Shakhar Smorodinsky

A geometric graph is a simple graph G = (V, E) with an embedding of the set V in the plane such that the points that represent V are in general position. A geometric graph is said to be k-locally Delaunay (or a D _k-graph) if for each edge (u, v) ∈ E there is a (Euclidean) disc d that contains u and v but no other vertex of G that is within k hops from u or v. The study of these graphs was recently motivated by topology control for wireless networks. We obtain the following results: (i) We prove that if G is a Di-graph on n vertices, then it has O(n^3/2) edges. (ii) We show that for any n there exist D₁-graphs with n vertices and Ω(n^4/3) edges. (iii) We prove that if G is a D ₂-graph on n vertices, then it has O(n) edges. This bound is worst-case asymptotically tight. As an application of the first result, we show that: (iv) The maximum size of a family of pairwise non-overlapping lenses in an arrangement of n unit circles in the plane is O(n^3/2). The first two results improve the best previously known upper and lower bounds of O(n ^5/3) and Ω(n) respectively (see [6]). The third result improves the best previously known upper bound of O(n log n). Finally, our last result improves the best previously known upper bound (for the more general case of not necessarily unit circles) of O(n^3/2k(n)) (see [1]), where k(n) = (log n)^O(α2(n)) and where α(n) is the extremely slowly growing inverse Ackermann's function.