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

Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

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 2 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].

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages94-101
Number of pages8
StatePublished - 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CitySan Francisco, CA
Period1/20/081/22/08

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles'. Together they form a unique fingerprint.

Cite this