Premium
Updating Polygonizations *
Author(s) -
Abellanas M.,
Garcia J.,
Hernbández G.,
Hurtado F.,
Serra O.,
Urrutia J.
Publication year - 1993
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.1230143
Subject(s) - monotone polygon , polygon (computer graphics) , convexity , computer science , regular polygon , polygon covering , position (finance) , set (abstract data type) , boundary (topology) , point (geometry) , combinatorics , constant (computer programming) , mathematics , point in polygon , algorithm , geometry , telecommunications , mathematical analysis , finance , frame (networking) , financial economics , economics , programming language
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?.