Minimum weight pseudo-triangulations
(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}}, }