论文标题
从其可见度图中计算伪三角形多边形的边界周期
Computing Boundary Cycle of a Pseudo-Triangle Polygon from its Visibility Graph
论文作者
论文摘要
简单多边形的可见性图是一个图形，具有相同的顶点集，其中一对顶点之间存在边缘，并且只有当通过它们的段完全位于多边形内部时。假定多边形边界上的每对相邻顶点都是可见的。因此，每个多边形的可见性图始终包含其边界边缘。这意味着我们在可见性图中始终具有哈密顿循环，该图确定了相应多边形边界上顶点的顺序。在本文中，我们提出了一种多项式时间算法，用于从其可见性图中确定伪三角形多边形的这种哈密顿周期。
Visibility graph of a simple polygon is a graph with the same vertex set in which there is an edge between a pair of vertices if and only if the segment through them lies completely inside the polygon. Each pair of adjacent vertices on the boundary of the polygon are assumed to be visible. Therefore, the visibility graph of each polygon always contains its boundary edges. This implies that we have always a Hamiltonian cycle in a visibility graph which determines the order of vertices on the boundary of the corresponding polygon. In this paper, we propose a polynomial time algorithm for determining such a Hamiltonian cycle for a pseudo-triangle polygon from its visibility graph.
