Updating Polygonizations*
Loading...
Date
1993
Journal Title
Journal ISSN
Volume Title
Publisher
Blackwell Science Ltd and the Eurographics Association
Abstract
In 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?.
Description
@article{10.1111:1467-8659.1230143,
journal = {Computer Graphics Forum},
title = {{Updating Polygonizations*}},
author = {Abellanas, M. and Garcia, J. and Hernbandez, G. and Hurtado, F. and Serra, O. and Urrutia, J.},
year = {1993},
publisher = {Blackwell Science Ltd and the Eurographics Association},
ISSN = {1467-8659},
DOI = {10.1111/1467-8659.1230143}
}