On the Union Complexity of Diametral Disks

  • Boris Aronov
  • Muriel Dulieu
  • Rom Pinchasi
  • Micha Sharir
Keywords: Gabriel graph, union complexity, diametral circles

Abstract

Let $S$ be a set of $n$ points in the plane, and let $\mathcal{D}$ be an arbitrary set of disks, each having a pair of points of $S$ as a diameter. We show that the combinatorial complexity of the union of $\mathcal{D}$ is $O(n^{3/2})$, and provide a lower bound construction with $\Omega(n^{4/3})$ complexity. If the points of $S$ are in convex position, the upper bound drops to $O(n\log n)$.

Published
2013-06-07
Article Number
P53