Closest and Farthest-Line Voronoi Diagrams in the Plane

Dartmouth Technical Report TR2007-593

	Mark C. Henle

Date: June 2007

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR2007-593.pdf> (5480KB)

Abstract:
  Voronoi diagrams are a geometric structure containing proximity
 information useful in efficiently answering a number of common
 geometric problems associated with a set of points in the plane.. They
 have applications in fields ranging from crystallography to biology.
 Diagrams of sites other than points and with different distance
 metrics have been studied.  This paper examines the Voronoi diagram of
 a set of lines, which has escaped study in the computational geometry
 literature. 
  The combinatorial and topological properties of the
 closest and farthest Voronoi diagrams are analyzed and O(n^2) and
 O(n log n) algorithms are presented for their computation
 respectively.

Note:
 Senior Honors Thesis.  Advisor: Robert L. Scot Drysdale