Date of Award
1994
Publication Type
Master Thesis
Degree Name
M.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
A plane-sweep method without using transformation but using two sweeps is used to construct the Voronoi diagram in $L\sb1\ (L\sb\infty,$ respectively) metric of a set of n point sites in O(nlogn) time and O(n) space. The two sweeps advance from opposite directions and produce two symmetrical data structures called the Left-to-Right Shortest-Path-Map and Right-to-Left Shortest-Path-Map. The two maps are then tailored to produce the desired Voronoi diagram. Source: Masters Abstracts International, Volume: 34-02, page: 0796. Adviser: Y. H. Tsin. Thesis (M.Sc.)--University of Windsor (Canada), 1994.
Recommended Citation
Wang, Jianan., "Constructing Voronoi diagrams in L(1) and L(infinity) metrics with two plane sweeps." (1994). Electronic Theses and Dissertations. 1555.
https://scholar.uwindsor.ca/etd/1555