Updating Polygonizations*

dc.contributor.authorAbellanas, M.en_US
dc.contributor.authorGarcia, J.en_US
dc.contributor.authorHernbandez, G.en_US
dc.contributor.authorHurtado, F.en_US
dc.contributor.authorSerra, O.en_US
dc.contributor.authorUrrutia, J.en_US
dc.date.accessioned2014-10-21T07:25:34Z
dc.date.available2014-10-21T07:25:34Z
dc.date.issued1993en_US
dc.description.abstractIn this paper we consider polygonizations that are robust when faced with changes in the vertices that are present or in their position. We analyze the dynamic maintenance of different types of polygonizations (monotone, star-shaped.) and we introduce monotone half-convex polygonizations that are specially interesting because they provide minimum cost per insertion or deletion. If we had to delete not only one point but several external layers of the set, then the onion polygonizations would be suited, because they can be updated in constant time. We also consider the case of points that can be moved to contiguous positions and we show how to polygonize the set for updating in linear time. We deal too with security problems for a polygon: What is the maximum distance the vertices of a polygon could be moved away of their position in such a way that the topology on the boundary of the polygon (or its convexity) remains the same?.en_US
dc.description.number3en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume12en_US
dc.identifier.doi10.1111/1467-8659.1230143en_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages143-152en_US
dc.identifier.urihttps://doi.org/10.1111/1467-8659.1230143en_US
dc.publisherBlackwell Science Ltd and the Eurographics Associationen_US
dc.titleUpdating Polygonizations*en_US
Files