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)$.
@article{10_37236_2681,
author = {Boris Aronov and Muriel Dulieu and Rom Pinchasi and Micha Sharir},
title = {On the union complexity of diametral disks},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {2},
doi = {10.37236/2681},
zbl = {1295.52028},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2681/}
}
TY - JOUR
AU - Boris Aronov
AU - Muriel Dulieu
AU - Rom Pinchasi
AU - Micha Sharir
TI - On the union complexity of diametral disks
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2681/
DO - 10.37236/2681
ID - 10_37236_2681
ER -
%0 Journal Article
%A Boris Aronov
%A Muriel Dulieu
%A Rom Pinchasi
%A Micha Sharir
%T On the union complexity of diametral disks
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2681/
%R 10.37236/2681
%F 10_37236_2681
Boris Aronov; Muriel Dulieu; Rom Pinchasi; Micha Sharir. On the union complexity of diametral disks. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2681
