Date of Award

1991

Degree Type

Thesis

Degree Name

M.C.Sc.

Department

Computer Science

First Advisor

Tsin, Y. H.,

Keywords

Computer Science.

Rights

CC BY-NC-ND 4.0

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.

Share

COinS