On the union complexity of diametral disks

Boris Aronov, Muriel Dulieu, Rom Pinchasi, Micha Sharir

    Research output: Contribution to journalArticlepeer-review


    Let S be a set of n points in the plane, and let 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 the disks in D is O(n3/2), and provide a lower bound construction with (n4/3) complexity. If the points of S are in convex position, the upper bound drops to O(n log n). The problem. Let S be a set of n points in the plane, and let E be a collection of unordered pairs of points of S. For each pair {a, b} ∈ E let Dab denote the disk with diameter ab; we refer to D ab as the diametral disk determined by {a, b}. Let D ab denote the resulting collection of disks, and let U denote their union. Let the complexity of U be measured by the number of its vertices, namely intersection points of two disk boundaries that lie on the boundary ∂U of U. In this paper we establish the following upper and lower bounds on the complexity of U.

    Original languageEnglish (US)
    JournalElectronic Journal of Combinatorics
    Issue number2
    StatePublished - Jun 7 2013

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics
    • Applied Mathematics


    Dive into the research topics of 'On the union complexity of diametral disks'. Together they form a unique fingerprint.

    Cite this