Date of Award

1994

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Tsin, Y. H.,

Keywords

Computer Science.

Rights

CC BY-NC-ND 4.0

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.

Share

COinS