Minimum weight triangulation by cutting out triangles
(2005) 16th International Symposium, ISAAC 2005 In Algorithms and computation / Lecture notes in computer science 3827. p.984994 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:
http://lup.lub.lu.se/record/209601
 author
 Grantson Borgelt, Magdalene ^{LU} ; Borgelt, C and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 2005
 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
 03029743
 16113349
 ISBN
 9783540309352
 DOI
 10.1007/11602613_98
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 2abf8357d6c14be5b127ed29343546cb (old id 209601)
 date added to LUP
 20080820 15:37:32
 date last changed
 20170813 03:27:25
@inproceedings{2abf8357d6c14be5b127ed29343546cb, 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 = {9783540309352}, issn = {03029743}, language = {eng}, pages = {984994}, publisher = {Springer}, title = {Minimum weight triangulation by cutting out triangles}, url = {http://dx.doi.org/10.1007/11602613_98}, volume = {3827}, year = {2005}, }