Advanced

Fixed parameter algorithms for the minimum weight triangulation problem

Grantson Borgelt, Magdalene LU ; Borgelt, Christian and Levcopoulos, Christos LU (2008) In International Journal of Computational Geometry and Applications 18(3). p.185-220
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 divide-and-conquer 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 divide-and-conquer 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:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
divide-and-conquer 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
0218-1959
DOI
10.1142/S0218195908002581
project
VR 2005-4085
language
English
LU publication?
yes
id
428efced-2903-4f93-9654-a65473b04f26 (old id 1254955)
date added to LUP
2008-10-17 15:03:35
date last changed
2017-01-01 05:40:38
@article{428efced-2903-4f93-9654-a65473b04f26,
  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 divide-and-conquer 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         = {0218-1959},
  keyword      = {divide-and-conquer algorithm,programming,dynamic,fixed parameter algorithm,minimum weight triangulation},
  language     = {eng},
  number       = {3},
  pages        = {185--220},
  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},
}