The Visible Perimeter of an Arrangement of Disks

Nivasch, Gabriel and Pach, János and Tardos, Gábor (2013) The Visible Perimeter of an Arrangement of Disks. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 364-375(Official URL:

Full text not available from this repository.


Given a collection of n opaque unit disks in the plane, we want to find a stacking order for them that maximizes their visible perimeter, the total length of all pieces of their boundaries visible from above. We prove that if the centers of the disks form a dense point set, i.e., the ratio of their maximum to their minimum distance is $O(n^{1/2})$, then there is a stacking order for which the visible perimeter is $Ω(n^{2/3})$. We also show that this bound cannot be improved in the case of the $n^{1/2}×n^{1/2}$ piece of a sufficiently small square grid. On the other hand, if the set of centers is dense and the maximum distance between them is small, then the visible perimeter is $O(n^{3/4})$ with respect to any stacking order. This latter bound cannot be improved either. These results partially answer some questions of Cabello, Haverkort, van Kreveld, and Speckmann.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_33
Classifications: P Styles > P.120 Circular
Z Theory > Z.250 Geometry

Actions (login required)

View Item View Item