Date of Award
1991
Publication Type
Master Thesis
Degree Name
M.C.Sc.
Department
Computer Science
Keywords
Computer Science.
Supervisor
Tsin, Y. H.,
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
The currently known sweep-line algorithm for constructing the nearest neighbor Voronoi diagram uses geometric transformation. This thesis presents another sweep-line algorithm without using geometric transformation. The algorithm conceptually consists of two steps. In the first step, two planar graphs called Left-Right Partial Voronoi Graph (LR-PVG) and Right-Left Partial Voronoi Graph (RL-PVG) are constructed in O(n log n) time and O(n) space using the two plane sweeps, where n is the number of points in the given point set. In the second step, a top-down non-recursive version of the divide-and-conquer method is used to merge LR-PVG and RL-PVG into the final Voronoi diagram in O(n log n) time and O(n) space. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis1991 .W354. Source: Masters Abstracts International, Volume: 30-04, page: 1390. Supervisor: Y. H. Tsin. Thesis (M.C.Sc.)--University of Windsor (Canada), 1991.
Recommended Citation
Wang, Sichao., "Constructing the Voronoi diagram using two sweeps." (1991). Electronic Theses and Dissertations. 1553.
https://scholar.uwindsor.ca/etd/1553