## Abstract

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(n^{3/2}), and provide a lower bound construction with (n^{4/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 language | English (US) |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 20 |

Issue number | 2 |

DOIs | |

State | Published - Jun 7 2013 |

## ASJC Scopus subject areas

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