BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR90-147
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Building Voronoi Diagrams for Convex Polygons in Linear Expected Time
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Chew, L. Paul
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1990
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/TR90-147.pdf
ABSTRACT::
	Let P be a list of points in the plane such that the points of
P taken in order form the vertices of a convex polygon.  We introduce
a simple, linear expected-time algorithm for finding the Voronoi
diagram of the points in P.  Unlike previous results on expected-time
algorithms for Voronoi diagrams, this method does not require any
assumptions about the distribution of points.  With minor
modifications, this method can be used to design fast algorithms for
certain problems involving unrestricted sets of points.  For example,
fast expected-time algorithms can be designed to delete a point from a
Voronoi diagram, to build an order k Voronoi diagram for an arbitrary
set of points, and to determine the smallest enclosing circle for
points at the vertices of a convex hull.
END:: ncstrl.dartmouthcs//TR90-147