Algorithms for Closest Point Problems: Practice and Theory

Dartmouth Technical Report PCS-TR92-185

	Peter Su

Date:  1992

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR92-185.pdf> (1148KB)

Abstract:
 	This paper describes and evaluates know sequential algorithms
 for constructing planar Voronoi diagrams and Delaunay triangulations.
 In addition, it describes a new incremental algorithm which is simple
 to understand and implement, but whose performance is competitive with
 all known methods.  The experiments in this paper are more than just
 simple benchmarks, they evaluate the expected performance of the
 algorithms in a precise and machine independent fashion.  Thus, the
 paper also illustrates how to use experimental tools to both
 understand the behaviour of different algorithms and to guide the
 algorithm design process.