"Constructing the Voronoi diagram using two sweeps." by Sichao. Wang

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

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