BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2007-593
ENTRY:: June 01, 2007
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Closest and Farthest-Line Voronoi Diagrams in the Plane
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Henle, Mark C.
DATE:: June 2007
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/TR2007-593.pdf
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
END:: ncstrl.dartmouthcs//TR2007-593