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

På svenska

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

Department/s

  • Computer Science

Publishing year

2007

Language

English

Pages

139-153

Publication/Series

Computational Geometry

Volume

38

Issue

3

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • approximation algorithms
  • pseudo triangulations
  • geometric networks
  • computational geometry

Status

Published

Project

  • VR 2005-4085

ISBN/ISSN/Other

  • ISSN: 0925-7721