Mostrar el registro sencillo del ítem
Ponencia
Minimum weight pseudo-triangulations
dc.creator | Gudmundsson, Joachim | es |
dc.creator | Levcopoulos, Christos | es |
dc.date.accessioned | 2017-03-02T07:50:02Z | |
dc.date.available | 2017-03-02T07:50:02Z | |
dc.date.issued | 2004 | |
dc.identifier.citation | Gudmundsson, J. y Levcopoulos, C. (2004). Minimum weight pseudo-triangulations. En 20th European Workshop on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/55072 | |
dc.description.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(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. | es |
dc.description.sponsorship | Netherlands Organisation for Scientific Research | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | 20th European Workshop on Computational Geometry (2004). | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Minimum weight pseudo-triangulations | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
idus.format.extent | 4 p. | es |
dc.eventtitle | 20th European Workshop on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Minimum weight pseudo-triangul ... | 119.5Kb | [PDF] | Ver/ | |