On the Union Complexity of Diametral Disks

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