The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Minimum weight pseudo-triangulations

Author

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.

Department/s

  • Computer Science

Publishing year

2004

Language

English

Pages

299-310

Publication/Series

FSTTCS 2004 / Lecture notes in computer science

Volume

3328

Document type

Conference paper

Publisher

Springer

Topic

  • 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

Project

  • VR 2002-4049

ISBN/ISSN/Other

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