Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles

ABSTRACT

Given a point set P in the plane, the Delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set P, whose two points p,q ∈ P are connected by an edge if and only if there is a rectangle parallel to the coordinate axes that contains p and q, but no other elements of P. The following question of Even et al. [ELRS03] was motivated by a frequency assignment problem in cellular telephone networks. Does there exist a constant c > 0 such that the Delaunay graph of any set of n points in general position in the plane contains an independent set of size at least cn? We answer this question in the negative, by proving that the largest independent set in a randomly and uniformly selected point set in the unit square is O(n log² log n/log n), with probability tending to 1. We also show that our bound is not far from optimal, as the Delaunay graph of a uniform random set of n points almost surely has an independent set of size at least cn/ log n.

We give two further applications of our methods. 1. We construct 2-dimensional n-element partially ordered sets such that the size of the largest independent sets of vertices in their Hasse diagrams is o(n). This answers a question of Matoušek and Přívětivý [MaP06] and improves a result of Kříž and Nešetřil [KrN91]. 2. For any positive integers c and d, we prove the existence of a planar point set with the property that no matter how we color its elements by c colors, we find an axis-parallel rectangle containing at least d points, all of which have the same color. This solves an old problem from [BrMP05].

REFERENCES

• 1: Deepak Ajwani , Khaled Elbassioni , Sathish Govindarajan , Saurabh Ray, Conflict-free coloring for rectangle ranges using O(n^.382) colors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248406]
• 2: Noga Alon , Shakhar Smorodinsky, Conflict-free colorings of shallow discs, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137864]
• 3: {BeCh87} J. Beck and W. Chen: Irregularities of Distribution. Cambridge Tracts in Mathematics 89, Cambridge University Press, Cambridge, 1987.
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: {BrMP05} P. Brass, W. Moser, and J. Pach: Research Problems in Discrete Geometry, Springer-Verlag, New York, 2005.
• 6: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 7: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 8: {DeH91} F. Dehne, A.-L. Hassenklover, J.-R. Sack, and N. Santoro: Computational Geometry algorithms for the systolic screen, Algorithmica 6 (1991), 734--761.
• 9: {ElM06} K. Elbassioni and N. H. Mustafa: Conflict-free colorings of rectangles ranges, in 23rd Internat. Symp. on Theoretical Aspects of Comp. Science (STACS 2006), 254--263.
• 10: Guy Even , Zvi Lotker , Dana Ron , Shakhar Smorodinsky, Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks, SIAM Journal on Computing, v.33 n.1, p.94-136, 2004 [doi>10.1137/S0097539702431840]
• 11: Amos Fiat , Meital Levy , Jiří Matoušek , Elchanan Mossel , János Pach , Micha Sharir , Shakhar Smorodinsky , Uli Wagner , Emo Welzl, Online conflict-free coloring for intervals, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 12: Ralf Hartmut Güting , Otto Nurmi , Thomas Ottmann, The direct dominance problem, Proceedings of the first annual symposium on Computational geometry, p.81-88, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323245]
• 13: R. H. Güting , O. Nurmi , T. Ottmann, Fast algorithms for direct enclosures and direct dominances, Journal of Algorithms, v.10 n.2, p.170-186, June 1989 [doi>10.1016/0196-6774(89)90011-4]
• 14: Sariel Har-Peled , Shakhar Smorodinsky, Conflict-Free Coloring of Points and Simple Regions in the Plane, Discrete & Computational Geometry, v.34 n.1, p.47-70, July 2005 [doi>10.1007/s00454-005-1162-6]
• 15: {JaT92} J. W. Jaromczyk and G. T. Toussaint: Relative neighborhood graphs and their relatives, Proc. IEEE 80 (1992), 1502--1517.
• 16: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 17: {KrN91} I. Kříž and J. Nešetřil: Chromatic number of Hasse diagrams, eyebrows and dimension, Order 8 (1991), 41--48.
• 18: {Ma99} J. Matoušek: Geometric Discrepancy. An Illustrated Guide. Algorithms and Combinatorics 18, Springer-Verlag, Berlin, 1999.
• 19: Jiří Matoušek , Aleš Přívětivý, The Minimum Independence Number of a Hasse Diagram, Combinatorics, Probability and Computing, v.15 n.3, p.473-475, May 2006 [doi>10.1017/S0963548305007200]
• 20: Mark H. Overmars , Derick Wood, On rectangular visibility, Journal of Algorithms, v.9 n.3, p.372-390, September 1988 [doi>10.1016/0196-6774(88)90028-4]
• 21: János Pach, Covering the plane with convex polygons, Discrete & Computational Geometry, v.1 n.1, p.73-81, 1986 [doi>10.1007/BF02187684]
• 22: {PaTT07} J. Pach, G. Tardos, and G. Tóth: Indecomposable coverings, in: Discrete Geometry, Combinatorics and Graph Theory, The China-Japan Joint Conference (CJCDGCGT 2005), Lecture Notes in Computer Science 4381, Springer, 2007, 135--148.
• 23: {PaT03} J. Pach and G. Tóth: Conflict-free colorings, in: Discrete and Computational Geometry, Algorithms Combin., Vol. 25, Springer, Berlin, 2003, 665--671.
• 24: Shakhar Smorodinsky, On the chromatic number of some geometric hypergraphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.316-323, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109593]
• 25: {Sp72} J. Spencer: Turán's theorem for κ-graphs, Discrete Math. 2 (1972), 183--186.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

General Terms:
Algorithms, Design, Theory