The largest empty annulus problem

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(n 3 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(n 3 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(nlogn) time and O(n) space.