Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Minimum weight pseudo-triangulations

In English

Författare

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(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.

Avdelning/ar

  • Computer Science

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

Ämne

  • Computer Science

Conference name

24th International Conference on Foundations of Software Technology and Theoretical Computer Science

Conference date

2004-12-16 - 2004-12-18

Conference place

Chennai, India

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISSN: 1611-3349
  • ISSN: 0302-9743