Back to search

University of Victoria (Canada)

Techniques for optimizing Fortune's plane-sweep algorithm for Voronoi diagrams

Abstract

dc:description.abstract

A Voronoi diagram is a fundamental geometric structure used in the field of computational geometry for encoding proximity information for a set of sites. Voronoi diagrams are used in many diverse disciplines. Thus, fast implementations of algo­rithms are needed for constructing them. This thesis describes general optimization techniques for plane-sweep algorithms and an efficient and stable implementation of Fortune's algo­rithm, an O(N log N) plane-sweep algorithm for constructing the two-dimensional Voronoi diagram on N point sites. A module-level approach to implementing and optimizing Fortune's plane-sweep algorithm is followed. This approach is oriented toward finding efficient data structures and fast geo­metric primitives. Efficiently implementable specifications of the plane-sweep data structures, an event queue and a sweep table, are detailed. The treatment is based on abstract data types and two efficient representations are described. The implementation uses an implicit heap for the event queue and a binary tree for the sweep table. The thesis also describes several formulations of the geometric primitives required by Fortune's algorithm. Robustness concerns play a role in the derivation of accurate primitives and in helping to remove redundancy and sources of possible inconsistencies. The implementation in this thesis is stable and well tested. After optimizing Fortune's algorithm, the resulting implemen­tation, Presto, compares favorably with other implementations for constructing the Voronoi diagram. For example, Presto computes the Voronoi diagram on 10000 sites in under seven seconds on a Sparcstation SLC with twelve megabytes of main memory. Thus, Presto can be used for solving various large geometric proximity problems.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
1991

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wong, Kenny

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1828/20184

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wong, Kenny. Techniques for optimizing Fortune's plane-sweep algorithm for Voronoi diagrams. Master of Science M.Sc. thesis, 1991. https://hdl.handle.net/1828/20184