The Largest Empty Circle ProblemMegan [email protected] largest empty circle (LEC) problem isdefined on a set P and consists of findingthe largest circle that contains no points inP and is also centered inside the convexhull of P . The LEC is always centered ateither a vertex on the Voronoi diagram forP or on an intersection between a Voronoiedge and the convex hull of P . Thus,finding the LEC consists of constructinga Voronoi diagram and convex hull for P ,then searching the Voronoi vertices andintersections between Voronoi edges andconvex hull edges to see where the LEClies. This paper presents a simple O(n[h+log n ]) solution to the largest empty circleproblem. Though previous work on thisproblem has found O(n log n) solutions,we find that for data sets which are some-what normally distributed, h is small andour simple algorithm performs well.1 IntroductionThe Largest Empty Circle (LEC) problem is definedon a set of points P and consists of locating thelargest circle that contains no points of P and is cen-tered inside the convex hull of P . Less formally, thisproblem finds the point q bounded by the convex hullwhich maximizes the distance to its nearest neighborp ∈ P ; this point is the center of the largest emptycircle. We constrain q to lie within the convex hullof P because otherwise we would simply choose thepoint at infinity as the center of the LEC.This problem is sometimes referred to as theToxic Waste Dump problem, because given the co-ordinates for a set of cities, the LEC problem wouldallow you to find the best site for a toxic wastedump by finding the location which is maximally farfrom every city. This might also be useful for plan-ning locations for new stores. For example, imag-ine you would like to build a new McDonald’s ina metropolitan ares that already has several dozenMcDonald’s stores. By computing the LEC on theset of existing McDonald’s restaurants, you couldselect a site for a new store which is maximallyfar from all existing stores to minimize competitionwith other McDonald’s restaurants and situate your-self near people who previously did not have a Mc-Donald’s nearby.The Voronoi diagram for the set P is a useful toolfor solving the LEC problem. The Voronoi diagramis a partition of the plane into convex faces suchthat given a set of points P , each face (hereafter,Voronoi cell) contains exactly one point p ∈ P andall points in the plane which are closer to p than toany other point in P . Points lying on the edges be-tween Voronoi cells are equidistant between the twopoints contained in the cells lying to either side ofthe edge. Given these properties, it seems intuitivethat the largest empty circle should be centered on aVoronoi vertex. Since the edges represent all pointswhich are equidistant to the two points they divide,it follows that a vertex, which is simply an intersec-tion between multiple Voronoi edges, would max-imizes the minimum distance to all nearby points.Any point that is not on a Voronoi vertex must becloser to one point than any other and as such anyempty circle we can draw around it will not be ofmaximal size.Based on the above principles, it seems that wemight simply be able to draw empty circles aroundall Voronoi vertices and see which is the largest.However, since we constrain our circle to be cen-tered inside the convex hull of P , we must beslightly more careful in our search for the LEC.First, we must consider only Voronoi vertices whichlie inside the convex hull of P . Second, we mustconsider what happens on the edges of the convexhull itself. At points where a Voronoi edge inter-sects a convex hull edge, the distances between eachof the two nearest points is maximized, since we areon a Voronoi edge. Such points must also be consid-ered as candidates for the center of the LEC.2 Related WorkThe earliest solution to the LEC problem waspresented by Shamos in his Ph.D. thesis (1978).Shamos presented an algorithm that, given theVoronoi diagram and the convex hull, could find thelargest empty circle in O(n) time. Unfortunately,this algorithm was based on the assumption that ev-ery convex hull edge is intersected by at most twoVoronoi edges, which is not always true, as latershown by Toussaint (1983). Because the originalShamos algorithm incorrectly assumes a maximumof two Voronoi edge intersections at each convexhull edge, it can miss intersections at edges withmore than two intersections with Voronoi edges and,as such, can fail to recognize the true LEC.Toussaint (1983) went on to present an algorithmwhich correctly finds the LEC in all cases. However,the Toussaint algorithm requires O(n log n) runningtime when given the convex hull and Voronoi di-agram. The algorithm first computes the largestempty circle about each Voronoi vertex which liesin the interior of the convex hull. This step requiresO(n log h) operations; there are O(n) Voronoi ver-tices for which we must do an O(log h) point loca-tion step to check for interiority to the convex hull(where h is the number of convex hull edges), andcomputing the largest empty circle about a point canbe done in constant time. Once all interior pointshave been considered, the algorithm computes all in-tersections between Voronoi edges and convex hulledges. Toussaint uses an O(log n) algorithm takenfrom Chazelle (1980) to find the intersections be-tween a line segment and a convex n-gon. Sincethere are O(n) Voronoi edges (de Berg et al., 2000),this step requires O(n log h) time overall. By check-ing all points interior to the convex hull and all in-tersection points between the Voronoi diagram andthe convex hull, all possible sites for the center ofthe LEC have been considered. All that remains isto report the point about which the largest circle wasdrawn. Toussaint thus finds the LEC in O(n log n)time.Later, Preparata and Shamos (1985) offer an im-proved version of Shamos’s original methods (1978)which no longer relies on the assumption that eachconvex hull edge is intersected by at most twoVoronoi edges. Preparata and Shamos describe anO(n) marching method for finding all intersectionsbetween the Voronoi edges and the convex hull,which is an improvement on Toussaint’s O(n log h)method. Preparata and Shamos do not go into detailabout how to check Voronoi vertices on the interiorof the convex hull to see if they might be the cen-ter of the largest empty circle. We can only assumethat they, like Toussaint, also require an O (n log h)technique for