Back to search

University of British Columbia

A fast heuristic for finding the minimum weight triangulation

Abstract

dc: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.

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
1997

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Beirouti, Ronald

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/6380

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

Beirouti, Ronald. A fast heuristic for finding the minimum weight triangulation. master's thesis, University of British Columbia, 1997. http://hdl.handle.net/2429/6380