No Access

A LOWER BOUND ON THE AREA OF A 3-COLOURED DISK PACKING

PETER BRASS

Department of Computer Science, City College, CUNY, New York, NY 10031, USA

Search for more papers by this author

FERRAN HURTADO

Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain

The author was partially supported by projects MEC MTM2006-01267 and Gen. Cat. 2005SGR00692.

Search for more papers by this author

BENJAMIN LAFRENIERE

David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada

The author was supported in part by NSERC.

Search for more papers by this author

, and

ANNA LUBIW

David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada

The author was supported in part by NSERC.

Search for more papers by this author

https://doi.org/10.1142/S0218195910003335Cited by:2 (Source: Crossref)

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²) algorithm to select a subset achieving a 1/2.77 bound. Finally, we discuss some results for other numbers of colours.

A preliminary version of this paper was presented at the 19th Canadian Conference on Computational Geometry (CCCG 2007).¹.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

P. Brasset al., A lower bound on the area of a 3-coloured disc packing, Proc. 19th Canadian Conf. Computational Geometry (CCCG 2007) pp. 101–104. Google Scholar
R. Rado, Proc. London Math. Soc. s 2-51(4), 241 (1947). Web of Science, Google Scholar
N. Ahmed and S. Keshav, IEEE Wireless Communications and Networking Conf. (WCNC 2006) 1, 511 (2006), DOI: 10.1109/WCNC.2006.1683516. Google Scholar
F. B. Abdesslemet al., On the feasibility of power control in current IEEE 802.11 devices, Proc. 4th IEEE Int. Conf. Pervasive Computing and Communications Workshops (PERCOMW '2006) pp. 468–473. Google Scholar
Cisco Systems, Inc. Channel Deployment Issues for 2.4-Ghz 802.11 WLANs, Retrieved April 15, 2007 , http: // www. cisco. com/ univercd/ cc/ td/ doc/ product/ wireless/ airo1200/ accsspts/ techref/ channel. pdf . Google Scholar
T. Asano, P. Brass and S. Sasahara, Disc covering problem with application to digital halftoning, Proc. Int. Conf. Computer Science and Applications (ICCSA 2004) pp. 11–21. Google Scholar
Z. Chenet al., J. Comb. Optim. 11(2), 203 (2006), DOI: 10.1007/s10878-006-7132-y. Crossref, Web of Science, Google Scholar
G. Evenet al., Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, Proc. 43rd Ann. IEEE Symp. Foundations of Computer Science (FOCS 2002) pp. 691–700. Google Scholar
N. Alon and S. Smorodinsky, Conflict-free colorings of shallow discs, Proc. 22nd Ann. ACM Symp. Computational Geometry (SoCG 2006) pp. 41–43. Google Scholar
A. Fiatet al., Online conflict-free coloring for intervals, Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA 2005) pp. 545–554. Google Scholar
S. Har-Peled and S. Smorodinsky, On conflict-free coloring of points and simple regions in the plane, Proc. 19th Ann. ACM Symp. Computational Geometry (SoCG 2003) pp. 114–123. Google Scholar
B. Bollobás, Elemente. der Mathematik 23, 60 (1968). Google Scholar
B. M. Chazelle and D. T. Lee, Computing 36(1–2), 1 (1986), DOI: 10.1007/BF02238188. Crossref, Web of Science, Google Scholar
A. Gajentaan and M. H. Overmars, Comput. Geom.: Th. Appl. 5, 165 (1995), DOI: 10.1016/0925-7721(95)00022-2. Crossref, Web of Science, Google Scholar
B. Aronov and S. Har-Peled, On approximating the depth and related problems, Proc. 16th ACM-SIAM Symp. Discrete Algorithms (SODA 2005) pp. 886–894. Google Scholar
B. Lafreniere, Packing Unit Disks, Master's Thesis, University of Waterloo, Waterloo ON, Canada (2008) , http://hdl.handle.net/10012/3907 . Google Scholar