BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR86-130
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Finding Largest Empty Circles with Location Constraints
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Chew, L. Paul
AUTHOR:: Drysdale, Robert L. Scot
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1986
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR86-130.pdf
ABSTRACT::
	Let S be a set of n points in the plane and let CH(S)
represent the convex hull of S.  The Largest Empty Circle (LEC)
problem is the problem of finding the largest circle centered with
CH(S) such that no point of S lies within the circle.  Shamos and Hoey
(SH75) outlined an algorithm for solving this problem in time O(n log
n) by first computing the Voronoi diagram, V(S), in time O(n log n),
then using V(S) and CH(S) to compute the largest empty circle in time
O(n).  In a recent paper [Tou83], Toussaint pointed out some problems
with the algorithm as outlined by Shamos and presented an algorithm
which, given V(S) and CH(S), solves the LEC problem in time O(n log
n).  In this note we show that Shamos' original claim was correct:
given V(S) and CH(S), the LEC problem can be solved in time O(n).
More generally, given V(S) and a convex k-gon P, the LEC centered
within P can be found in time O(k+n).  We also improve on an algorithm
given by Toussaint for computing the LEC when the center is
constrained to lie within an arbitrary simple polygon.  Given a set S
of n points and an arbitrary simple k-gon P, the largest empty circle
centered within P can be found in time O(kn + n log n).  This becomes
O(kn) if the Voronoi diagram of S is already given.
END:: ncstrl.dartmouthcs//TR86-130