Ponencia
Minimum weight pseudo-triangulations
Autor/es | Gudmundsson, Joachim
Levcopoulos, Christos |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-02 |
Publicado en |
|
Resumen | 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(wt(M(S))· log ... 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(wt(M(S))· log n) which is shown to be asymptotically worst-case optimal, i.e., there exists a point set S for which every pseudotriangulation has weight Ω(log n·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. |
Cita | Gudmundsson, J. y Levcopoulos, C. (2004). Minimum weight pseudo-triangulations. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Minimum weight pseudo-triangul ... | 119.5Kb | [PDF] | Ver/ | |