@inproceedings{e353ad34cb444b67ae1031775edbf2cd,

title = "Minimum weight pseudo-triangulations (Extended abstract)",

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.",

author = "J. Gudmundsson and C. Levcopoulos",

year = "2004",

doi = "10.1007/978-3-540-30538-5_25",

language = "English",

isbn = "3-540-24058-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "299--310",

editor = "K. Lodaya and M. Mahajan",

booktitle = "Foundations of Software Technology and Theoretical Computer Science (Proceedings 24th Conference, FSTTCS 2004, Chennai, India, December 16-18, 2004)",

address = "Germany",

}