- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Topology building and random polygon generation
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Topology building and random polygon generation Zhu, Chongjian
Abstract
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).
Item Metadata
Title |
Topology building and random polygon generation
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1994
|
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).
|
Extent |
1870341 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-02-27
|
Provider |
Vancouver : University of British Columbia Library
|
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.
|
DOI |
10.14288/1.0051255
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
1994-05
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
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.