Javascript is not activated in your browser. This website needs javascript activated to work properly.
Du är här

Minimum weight pseudo-triangulations

Publiceringsår: 2004
Språk: Engelska
Sidor: 299-310
Publikation/Tidskrift/Serie: FSTTCS 2004 / Lecture notes in computer science
Volym: 3328
Dokumenttyp: Konferensbidrag
Förlag: Springer Berlin / Heidelberg


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.



  • Technology and Engineering


24th International Conference on Foundations of Software Technology and Theoretical Computer Science
Chennai, India
  • VR 2002-4049
  • ISSN: 0302-9743

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen