Minimum weight pseudo-triangulations
Gudmundsson, Joachim and Levcopoulos, Christos LU
(2004)
24th International Conference on Foundations of Software Technology and Theoretical 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:
https://lup.lub.lu.se/record/633303
- author
- Gudmundsson, Joachim
and Levcopoulos, Christos
LU
- organization
- publishing date
- 2004
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 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
- conference location
- Chennai, India
- conference dates
- 2004-12-16 - 2004-12-18
- 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
- 2016-04-01 11:34:05
- date last changed
- 2024-01-07 12:43:41
@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}},
doi = {{10.1007/b104325}},
volume = {{3328}},
year = {{2004}},
}