## Electronic Theses and Dissertations

1994

Thesis

M.Sc.

Computer Science

Tsin, Y. H.,

#### Keywords

Computer Science.

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.

COinS