Updating Polygonizations*

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?.