On the Union Complexity of Diametral Disks

Boris Aronov, Muriel Dulieu, Rom Pinchasi, Micha Sharir

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)$.


Keywords


Gabriel graph; union complexity; diametral circles

Full Text: PDF