Packing circles in a circle is a classic mathematical problem, which has been studied for a long time. Recently, this problem received a great deal of applications in the study of wireless networks. Those applications are related to many combinatorial optimization problems raised in wireless networks. In analyzing approximation algorithms for those combinatorial optimization problems, it is required to establish an upper bound for the number of untouched unit circles, which can be packed into a circle of radius r, where a unit circle is a circle with diameter 1. This bound can be easily derived from some classic bounds for the number of unit circles packed into a circle. Moreover, analysis of those approximation algorithms also promoted some new problems about packing circles in circles. In this chapter, a state of the art on the developments in this research direction is presented.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Packing Circles in Circles and Applications

  • Yingli Ran,
  • Zhao Zhang,
  • Weili Wu,
  • Ling Ding,
  • Qinghai Liu,
  • Lidong Wu

摘要

Packing circles in a circle is a classic mathematical problem, which has been studied for a long time. Recently, this problem received a great deal of applications in the study of wireless networks. Those applications are related to many combinatorial optimization problems raised in wireless networks. In analyzing approximation algorithms for those combinatorial optimization problems, it is required to establish an upper bound for the number of untouched unit circles, which can be packed into a circle of radius r, where a unit circle is a circle with diameter 1. This bound can be easily derived from some classic bounds for the number of unit circles packed into a circle. Moreover, analysis of those approximation algorithms also promoted some new problems about packing circles in circles. In this chapter, a state of the art on the developments in this research direction is presented.