Advanced

Minimum weight pseudo-triangulations

Gudmundsson, Joachim and Levcopoulos, Christos LU (2004) 24th International Conference on Foundations of Software Technology and Theoretical Computer Science In FSTTCS 2004 / Lecture notes in computer science 3328. p.299-310
Abstract
We consider the problem of computing a minimum weight pseudo-triangulation of a set S of n points in the plane. We first present an O(nlogn)-time algorithm that produces a pseudo-triangulation of weight O(wt(M(S))logn) which is shown to be asymptotically worst-case optimal, i.e., there exists a point set S for which every pseudo-triangulation has weight Omega(wt(M(S))logn), where wt(M(S)) is the weight of a minimum spanning tree of S. We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon.
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
FSTTCS 2004 / Lecture notes in computer science
volume
3328
pages
299 - 310
publisher
Springer
conference name
24th International Conference on Foundations of Software Technology and Theoretical Computer Science
external identifiers
  • scopus:35048822072
ISSN
0302-9743
1611-3349
DOI
10.1007/b104325
project
VR 2002-4049
language
English
LU publication?
yes
id
40a1f4d3-bc8b-41d9-8062-2978aa9b9ca0 (old id 633303)
date added to LUP
2007-11-28 15:01:30
date last changed
2017-01-01 04:20:23
@inproceedings{40a1f4d3-bc8b-41d9-8062-2978aa9b9ca0,
  abstract     = {We consider the problem of computing a minimum weight pseudo-triangulation of a set S of n points in the plane. We first present an O(nlogn)-time algorithm that produces a pseudo-triangulation of weight O(wt(M(S))logn) which is shown to be asymptotically worst-case optimal, i.e., there exists a point set S for which every pseudo-triangulation has weight Omega(wt(M(S))logn), where wt(M(S)) is the weight of a minimum spanning tree of S. We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon.},
  author       = {Gudmundsson, Joachim and Levcopoulos, Christos},
  booktitle    = {FSTTCS 2004 / Lecture notes in computer science},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {299--310},
  publisher    = {Springer},
  title        = {Minimum weight pseudo-triangulations},
  url          = {http://dx.doi.org/10.1007/b104325},
  volume       = {3328},
  year         = {2004},
}