Back to search

University of British Columbia

Topology building and random polygon generation

Abstract

dc:description

In the island adoption problem from geographical information system we are asked to identify which islands are located in which lakes. This problem translates directly to polygon nesting in computational geometry: given a set of polygons, find their nesting structure. We present our research into a broader nesting problem, namely connected component nesting, beginning with the underlying concept of topology-building and a related issue of random polygon generation. Topology building is a process of structuring data. We develop a plane sweep al gorithm for building a quad-edge data structure that captures the topological structure of connected components of a set of line segments. The algorithm starts with a data structure representing a single edge then adds edges into the data structure at each step while sweeping across the connected components The algorithm’s time complexity is determined by the time to sort the vertices of the line segments. We develop two approaches for obtaining the nesting structure of polygons. The first adopts a basic idea of Bajaj and Dey [1], but introduces a new notch definition to simplify their algorithm. The second generalizes the nesting problem to a broader class including the nesting of connected components. We present a sweep algorithm, based on a union-find data structure, that computes the nesting of the connected components. In order to test and verify the time complexity of our polygon nesting algorithm, we present an algorithm that generates x-monotone polygons uniformly at random over a vertex set of n points. This algorithm scans the point set to calculate the total number of monotone polygons that can be created, then reverses the scan to generate a random monotone polygon. This process generates a random polygon over the n vertices in 0(K) time, where n K n2 is the number edges of the visibility graph of the x-monotone chain whose vertices are the given n points. The space complexity of our algorithm is 0(n).

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1994

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhu, Chongjian

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/5246

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhu, Chongjian. Topology building and random polygon generation. master's thesis, University of British Columbia, 1994. http://hdl.handle.net/2429/5246