On local transformation of polygons with visibility properties
On local transformation of polygons with visibility properties
复制标题
具有可见性的多边形的局部变换
DOI：
10.1016/s0304-3975(01)00409-1
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
F. Hurtado
中科院分区：
文献类型：
--
作者：
Carmen Hernando;Michael E. Houle;F. Hurtado
枚举对象类的一种策略是局部变换，在局部变换中，通过对同一类中先前访问的对象进行小的修改来产生类的新对象。当局部变换可能时，该操作可用于通过随机游动生成类的对象，并作为模拟退火法等优化启发式算法的基础。对于固定点集上的一般简单多边形，其上的多边形类是否通过恒定大小的局部变换来连接仍是未知的。在这篇文章中，我们展示了一个简单的局部变换，它连接了下列多边形类：单调、x-单调、星形、(弱)边可见和(弱)外可见。后一类特别有趣，因为它是已知在局部变换下连接的最一般的多边形类。对于每一个多边形类，我们还提供了将类中的一个成员转换为任何其他成员所需的最小操作数的渐近紧的最坏情况上界。
One strategy for the enumeration of a class of objects is local transformation, in which new objects of the class are produced by means of a small modification of a previously-visited object in the same class. When local transformation is possible, the operation can be used to generate objects of the class via random walks, and as the basis for such optimization heuristics as simulated annealing. For general simple polygons on fixed point sets, it is still not known whether the class of polygons on the set is connected via a constant-size local transformation. In this paper, we exhibit a simple local transformation for which the following polygon classes are connected: monotone, x-monotone, star-shaped, (weakly) edge-visible and (weakly) externally visible. The latter class is particularly interesting as it is the most general polygon class known to be connected under local transformation. For each of the polygon classes, we also provide asymptotically-tight worst-case upper bounds on the minimum number of operations required to transform one member of the class to any other.