Back to search

Hosted by Utah State University Libraries

Exact Generalized Voronoi Diagram Computation using a Sweepline Algorithm

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Hosted by Utah State University Libraries

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Marsden, Daniel
Contributors dc:contributor
  • John Edwards
  • Xiaojun Qi
  • Minghui Jiang

Subjects

dc:subject × 6

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Utah State University
Base URL
digitalcommons.usu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Marsden, Daniel. Exact Generalized Voronoi Diagram Computation using a Sweepline Algorithm. Thesis thesis, Hosted by Utah State University Libraries, https://digitalcommons.usu.edu/etd/7947