Advanced

Minimum weight triangulation by cutting out triangles

Grantson Borgelt, Magdalene LU ; Borgelt, C and Levcopoulos, Christos LU (2005) 16th International Symposium, ISAAC 2005 In Algorithms and computation / Lecture notes in computer science 3827. p.984-994
Abstract
We describe a fixed parameter algorithm for computing the minimum weight triangulation (MWT) of a simple polygon with (n - k) vertices on the perimeter and k hole vertices in the interior, that is, for a total of n vertices. Our algorithm is based on cutting out empty triangles (that is, triangles not containing any holes) from the polygon and processing the parts or the rest of the polygon recursively. We show that with our algorithm a minimum weight triangulation can be found in time at most O(n(3)k! k), and thus in O(n(3)) if k is constant. We also note that k! can actually be replaced by b(k) for some constant b. We implemented our algorithm in Java and report experiments backing our analysis.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithms and computation / Lecture notes in computer science
volume
3827
pages
984 - 994
publisher
Springer
conference name
16th International Symposium, ISAAC 2005
external identifiers
  • wos:000234885900098
  • scopus:33744953726
ISSN
0302-9743
1611-3349
ISBN
978-3-540-30935-2
DOI
10.1007/11602613_98
project
VR 2002-4049
language
English
LU publication?
yes
id
2abf8357-d6c1-4be5-b127-ed29343546cb (old id 209601)
date added to LUP
2008-08-20 15:37:32
date last changed
2017-08-13 03:27:25
@inproceedings{2abf8357-d6c1-4be5-b127-ed29343546cb,
  abstract     = {We describe a fixed parameter algorithm for computing the minimum weight triangulation (MWT) of a simple polygon with (n - k) vertices on the perimeter and k hole vertices in the interior, that is, for a total of n vertices. Our algorithm is based on cutting out empty triangles (that is, triangles not containing any holes) from the polygon and processing the parts or the rest of the polygon recursively. We show that with our algorithm a minimum weight triangulation can be found in time at most O(n(3)k! k), and thus in O(n(3)) if k is constant. We also note that k! can actually be replaced by b(k) for some constant b. We implemented our algorithm in Java and report experiments backing our analysis.},
  author       = {Grantson Borgelt, Magdalene and Borgelt, C and Levcopoulos, Christos},
  booktitle    = {Algorithms and computation / Lecture notes in computer science},
  isbn         = {978-3-540-30935-2},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {984--994},
  publisher    = {Springer},
  title        = {Minimum weight triangulation by cutting out triangles},
  url          = {http://dx.doi.org/10.1007/11602613_98},
  volume       = {3827},
  year         = {2005},
}