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:
https://lup.lub.lu.se/record/686737
- author
- Gudmundsson, Joachim
and Levcopoulos, Christos
LU
- organization
- publishing date
- 2007
- 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
- 2016-04-01 17:13:45
- date last changed
- 2022-01-29 01:17:07
@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}},
keywords = {{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}},
doi = {{10.1016/j.comgeo.2007.05.004}},
volume = {{38}},
year = {{2007}},
}