Advanced

Minimum weight pseudo-triangulations

Gudmundsson, Joachim and Levcopoulos, Christos LU (2007) In Computational Geometry 38(3). p.139-153
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(n log n)-time algorithm that produces a pseudo-triangulation of weight O(log n - wt(M(S))) which is shown to be asymptotically worst-case optimal, i.e., there exists a point set S for which every pseudo-triangulation has weight 0 (log n - wt(M(S))), where wt(.M(S)) is the weight of a minimum weight 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. (C) 2007 Elsevier B.V. All rights reserved.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
approximation algorithms, pseudo triangulations, geometric networks, computational geometry
in
Computational Geometry
volume
38
issue
3
pages
139 - 153
publisher
Elsevier
external identifiers
  • wos:000249488900002
  • scopus:84867947111
ISSN
0925-7721
DOI
10.1016/j.comgeo.2007.05.004
project
VR 2005-4085
language
English
LU publication?
yes
id
97fafa88-bef0-4b9f-b654-a4da7390f451 (old id 686737)
date added to LUP
2007-12-12 08:33:20
date last changed
2017-01-01 07:27:52
@article{97fafa88-bef0-4b9f-b654-a4da7390f451,
  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(n log n)-time algorithm that produces a pseudo-triangulation of weight O(log n - wt(M(S))) which is shown to be asymptotically worst-case optimal, i.e., there exists a point set S for which every pseudo-triangulation has weight 0 (log n - wt(M(S))), where wt(.M(S)) is the weight of a minimum weight 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. (C) 2007 Elsevier B.V. All rights reserved.},
  author       = {Gudmundsson, Joachim and Levcopoulos, Christos},
  issn         = {0925-7721},
  keyword      = {approximation algorithms,pseudo triangulations,geometric networks,computational geometry},
  language     = {eng},
  number       = {3},
  pages        = {139--153},
  publisher    = {Elsevier},
  series       = {Computational Geometry},
  title        = {Minimum weight pseudo-triangulations},
  url          = {http://dx.doi.org/10.1016/j.comgeo.2007.05.004},
  volume       = {38},
  year         = {2007},
}