Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles
Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles
复制标题
有效构建有障碍的简单多边形的可见性图
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
S. Maheshwari
中科院分区：
文献类型：
--
作者：
S. Kapoor;S. Maheshwari
本文介绍了一种输出敏感的方案，以构建具有M障碍物和N顶点的简单多边形的可见度图（| e | + t + m log n）时间| e | |是可见度图的大小，t是用障碍物三角分析简单多边形所需的时间。我们将空间的分区分配到称为走廊的地区，以减轻建筑的努力。我们的算法很简单，使用的数据结构仅是链接的列表。
This paper describes an output-sensitive scheme to construct the visibility graph of a simple polygon with m obstacles and n vertices in optimal O(|E| +T + m log n ) time where |E| is the size of the visibility graph and T is the time required to triangulate the simple polygon with obstacles. We use a partition of the space into regions called corridors which eases the efforts of the construction. Our algorithms are simple and the data structures used are only linked lists.