Fixed parameter algorithms for the minimum weight triangulation problem
(2008) In International Journal of Computational Geometry and Applications 18(3). p.185220 Abstract
 We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n  k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divideandconquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we... (More)
 We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n  k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divideandconquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1254955
 author
 Grantson Borgelt, Magdalene ^{LU} ; Borgelt, Christian and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 2008
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 divideandconquer algorithm, programming, dynamic, fixed parameter algorithm, minimum weight triangulation
 in
 International Journal of Computational Geometry and Applications
 volume
 18
 issue
 3
 pages
 185  220
 publisher
 World Scientific
 external identifiers

 wos:000257540600002
 scopus:45749150320
 ISSN
 02181959
 DOI
 10.1142/S0218195908002581
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 428efced29034f939654a65473b04f26 (old id 1254955)
 date added to LUP
 20081017 15:03:35
 date last changed
 20170101 05:40:38
@article{428efced29034f939654a65473b04f26, abstract = {We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n  k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divideandconquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation.}, author = {Grantson Borgelt, Magdalene and Borgelt, Christian and Levcopoulos, Christos}, issn = {02181959}, keyword = {divideandconquer algorithm,programming,dynamic,fixed parameter algorithm,minimum weight triangulation}, language = {eng}, number = {3}, pages = {185220}, publisher = {World Scientific}, series = {International Journal of Computational Geometry and Applications}, title = {Fixed parameter algorithms for the minimum weight triangulation problem}, url = {http://dx.doi.org/10.1142/S0218195908002581}, volume = {18}, year = {2008}, }