TY - GEN
T1 - Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles
AU - Chen, Xiaomin
AU - Pach, János
AU - Szegedy, Mario
AU - Tardos, Gábor
PY - 2008
Y1 - 2008
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=78650421910&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78650421910&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:78650421910
SN - 9780898716474
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 94
EP - 101
BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 20 January 2008 through 22 January 2008
ER -