Minimum weight pseudo-triangulations

Summary, in English

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.

• Författare: Joachim Gudmundsson; Christos Levcopoulos
• Avdelning/ar: Computer Science
• Publiceringsår: 2007
• Språk: Engelska
• Sidor: 139-153
• Publikation/Tidskrift/Serie: Computational Geometry
• Volym: 38
• Issue: 3
• Länkar: http://dx.doi.org/10.1016/j.comgeo.2007.05.004
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Computer Science
• Nyckelord: approximation algorithms; pseudo triangulations; geometric networks; computational geometry
• Status: Published
• Projekt: VR 2005-4085
• ISBN/ISSN/Övrigt: ISSN: 0925-7721