Minimum weight triangulation by cutting out triangles
Grantson Borgelt, Magdalene LU ; Borgelt, C and Levcopoulos, Christos LU
(2005)
16th International Symposium, ISAAC 2005
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:
https://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
- host publication
- Algorithms and computation / Lecture notes in computer science
- volume
- 3827
- pages
- 984 - 994
- publisher
- Springer
- conference name
- 16th International Symposium, ISAAC 2005
- conference location
- Sanya, Hainan, China
- conference dates
- 2005-12-19 - 2005-12-21
- external identifiers
-
- wos:000234885900098
- scopus:33744953726
- ISSN
- 1611-3349
- 0302-9743
- 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
- 2016-04-01 11:34:03
- date last changed
- 2024-02-22 21:36:06
@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 = {{1611-3349}},
language = {{eng}},
pages = {{984--994}},
publisher = {{Springer}},
title = {{Minimum weight triangulation by cutting out triangles}},
url = {{http://dx.doi.org/10.1007/11602613_98}},
doi = {{10.1007/11602613_98}},
volume = {{3827}},
year = {{2005}},
}