Back to Search
Start Over
A LOWER BOUND ON THE AREA OF A 3-COLOURED DISK PACKING.
- Source :
- International Journal of Computational Geometry & Applications; Jun2010, Vol. 20 Issue 3, p341-360, 20p, 11 Diagrams, 1 Graph
- Publication Year :
- 2010
-
Abstract
- Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1/4 and proved 1/4.41. Motivated by the problem of channel assignment for wireless access points, in which use of 3 channels is a standard practice, we consider a variant where the selected subset of disks must be 3-colourable with disks of the same colour pairwise-disjoint. For this variant of the problem, we conjecture that it is always possible to cover at least 1/1.41 of the union area and prove 1/2.09. We also provide an O(n<superscript>2</superscript>) algorithm to select a subset achieving a 1/2.77 bound. Finally, we discuss some results for other numbers of colours. [ABSTRACT FROM AUTHOR]
- Subjects :
- PLANE geometry
ALGORITHMS
GEOMETRY
OPTICAL disks
ALGEBRA
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 20
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 51993801
- Full Text :
- https://doi.org/10.1142/S0218195910003335