Minimum weight pseudo-triangulations (Extended abstract)

J. Gudmundsson, C. Levcopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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 O(logn.wt(M(S)) , 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.
Original languageEnglish
Title of host publicationFoundations of Software Technology and Theoretical Computer Science (Proceedings 24th Conference, FSTTCS 2004, Chennai, India, December 16-18, 2004)
EditorsK. Lodaya, M. Mahajan
Place of PublicationBerlin
PublisherSpringer
Pages299-310
ISBN (Print)3-540-24058-6
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
Volume3328
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Minimum weight pseudo-triangulations (Extended abstract)'. Together they form a unique fingerprint.

Cite this