On the union complexity of diametral disks (Q396766): Difference between revisions

Summary: 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)\).