- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A fast heuristic for finding the minimum weight triangulation
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
A fast heuristic for finding the minimum weight triangulation Beirouti, Ronald
Abstract
No polynomial time algorithm is known to compute the minimum weight triangulation (MWT) of a point set. In this thesis we present an efficient implementation of the LMTskeleton heuristic. This heuristic computes a subgraph of the MWT of a point set from which the MWT can usually be completed. For uniformly distributed sets of tens of thousands of points our algorithm constructs the exact MWT in expected linear time and space. A fast heuristic, other than being usefull in areas such as stock cutting, finite element analysis, and terrain modeling, allows to experiment with different point sets in order to explore the complexity of the MWT problem. We present point sets constructed with this implementation such that the LMT-skeleton heuristic does not produce a complete graph and can not compute the MWT in polynomial time, or that can be used to prove the NP-Hardness of the MWT problem.
Item Metadata
| Title |
A fast heuristic for finding the minimum weight triangulation
|
| Creator | |
| Publisher |
University of British Columbia
|
| Date Issued |
1997
|
| Description |
No polynomial time algorithm is known to compute the minimum weight triangulation
(MWT) of a point set. In this thesis we present an efficient implementation of the LMTskeleton
heuristic. This heuristic computes a subgraph of the MWT of a point set from
which the MWT can usually be completed. For uniformly distributed sets of tens of
thousands of points our algorithm constructs the exact MWT in expected linear time
and space.
A fast heuristic, other than being usefull in areas such as stock cutting, finite element
analysis, and terrain modeling, allows to experiment with different point sets in order to
explore the complexity of the MWT problem. We present point sets constructed with
this implementation such that the LMT-skeleton heuristic does not produce a complete
graph and can not compute the MWT in polynomial time, or that can be used to prove
the NP-Hardness of the MWT problem.
|
| Extent |
3023953 bytes
|
| Genre | |
| Type | |
| File Format |
application/pdf
|
| Language |
eng
|
| Date Available |
2009-03-24
|
| 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.0051592
|
| URI | |
| Degree | |
| Program | |
| Affiliation | |
| Degree Grantor |
University of British Columbia
|
| Graduation Date |
1997-11
|
| 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.