THE LARGEST EMPTY ANNULUS PROBLEM
José Miguel Díaz-Báñez, F. Hurtado, Henk Meijer, David D. Rappaport, J. Antoni Sellarès · International Journal of Computational Geometry & Applications · 2003
Given a set of n points S in the Euclidean plane, we address the problem of computing an annulus A, (open region between two concentric circles) of largest width, that partitions S into a subset of points inside and a subset of points outside the circles, such that no point p∈S lies in the interior of A. This problem can be considered as a maximin facility location problem for n points such that the facility is a circumference. We give a characterization of the centres of annuli which are locally optimal and we show that the problem can be solved in O(n3 log n) time and O (n) space. We also consider the case in which the number of points in the inner circle is a fixed value k. When k∈O(n) our algorithm runs in O(n3 log n) time and O(n) space, furthermore, we can simultaneously optimize for all values of k within the same time bound. When k is small, that is a fixed constant, we can solve the problem in O(n log n) time and O(n) space.