Physical Sciences and Mathematics Commons^™

Exact Generalized Voronoi Diagram Computation Using A Sweepline Algorithm, Daniel Marsden

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Voronoi Diagrams can provide useful spatial information. Little work has been done on computing exact Voronoi Diagrams when the sites are more complex than a point. We introduce a technique that measures the exact Generalized Voronoi Diagram from points, line segments and, connected lines including lines that connect to form simple polygons. Our technique is an extension of Fortune’s method. Our approach treats connected lines (or polygons) as a single site.