Updating Polygonizations *
Updating Polygonizations *
复制标题
更新多边形*
DOI：
10.1111/1467-8659.1230143
复制
发表时间：
1993
影响因子：
2.5
通讯作者：
J. Urrutia
中科院分区：
文献类型：
--
作者：
M. Abellanas;J. García;Gregorio Hernández;F. Hurtado;O. Serra;J. Urrutia
在这篇文章中，我们考虑了当面对顶点的变化或其位置的变化时具有健壮性的多边形化。我们分析了不同类型的多边形化(单调、星形…)的动态维护我们引入了单调半凸多边形化，这是特别有趣的，因为它们提供了最小的每次插入或删除成本。如果我们不仅要删除集合的一个点，而且要删除集合的几个外层，那么洋葱多边形化将是合适的，因为它们可以在固定的时间内更新。我们还考虑了点可以移动到连续位置的情况，并展示了如何在线性时间内对集合进行多边形化以进行更新。我们还处理了多边形的安全问题：在使多边形边界上的拓扑(或其凸度)保持不变的情况下，多边形顶点可以远离其位置的最大距离是多少？
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?.