Meny

Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Minimum weight pseudo-triangulations

Författare:
Publiceringsår: 2007
Språk: Engelska
Sidor: 139-153
Publikation/Tidskrift/Serie: Computational Geometry: Theory and Applications
Volym: 38
Nummer: 3
Dokumenttyp: Artikel
Förlag: Elsevier Science B.V.

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • approximation algorithms
  • pseudo triangulations
  • geometric networks
  • computational geometry

Övriga

Published
  • VR 2005-4085
Yes
  • ISSN: 0925-7721

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