The visible perimeter of an arrangement of disks

Original · EN

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¹/2), then there is a stacking order for which the visible perimeter is Omega(n²/3). We also show that this bound cannot be improved in the case of a sufficiently small n¹/2 by n¹/2 uniform 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³/4) with respect to any stacking order. This latter bound cannot be improved either. Finally, we address the case where no more than c disks can have a point in common. These results partially answer some questions of Cabello, Haverkort, van Kreveld, and Speckmann.