Worst-case optimal algorithms for constructing visibility polygons with holes
Worst-case optimal algorithms for constructing visibility polygons with holes
复制标题
构造带孔可见性多边形的最坏情况最优算法
DOI：
10.1145/10515.10517
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
J. O'Rourke
中科院分区：
文献类型：
--
作者：
S. Suri;J. O'Rourke
EIGindy和Avis [EA]考虑了从多边形内的点确定可见性多边形的问题。他们的算法运行在最优的O（n）时间和空间，其中n是给定多边形的顶点数。后来，他们的结果被EIGindy [Eli，Lee和Lin ILL I]推广到从边可见多边形。这两个独立发现的O（nlogn）算法解决这个问题。Very recently最近|.艾. [GH]提出了一个最优0（n）时间算法。这些算法都不适用于有洞的多边形。在本文中，我们考虑的问题，计算可见性多边形q内的多边形P可能有洞。我们的第一个结果是一个算法计算的可见性多边形从一个给定的点内P。该算法的运行时间为0（nlogn），通过对n个正整数排序问题的约化证明该算法是最优的（Aaano st. al，[AA]独立获得了该结果）。接下来我们考虑从线段确定可见性多边形的问题。作为我们的主要结果，我们建立了一个最坏的容易下界N（n 4）显式计算的可见性多边形的边界从一条线段在其他线段的存在，并设计了一个最佳的算法来构建的边界。如果可见性多边形可以表示为多个多边形的并集，我们还提出了一个0（n2）时空算法。后者的算法也被证明是最佳的最坏的情况下。
EIGindy and Avis [EA] considered the problem of determining the visibility polygon from a point inside a polygon. Their algorithm runs in optimal O(n ) time and space, where n is the number of the vertices of the given polygon. Later their result was generalized to visibility polygons from an edge by EIGindy [Eli, and Lee and Lin ILL I. Both independently discovered O(nlogn) algorithms for this problem. Very recently Guibas e|. ai. [GH] have proposed an optimal 0 ( n ) time algorithm. None of these algorithms work for polygons with holes. In this paper we consider the problem of computing visibility polygon.q inside a polygon P that may have holes. Our first result is an algorithm for computing the visibility polygon from a given point inside P . The algorithm runs in 0 (nlogn) time, which is proved to be optimal by reduction from the problem of sorting n positive integers (Aaano st. al, [AA] have obtained this result independently). Next we consider the problem of determining the visibility polygon from a line segment. As our main result, we establish a worst-ease lower bound of N(n 4) for explicitly computing the boundary of the visibility polygon from a line segment in the presence of other line segments, and design an optimal algorithm to construct the boundary. We also present an 0 (n 2) time and space algorithm if the visibility polygon can be represented as a union of several polygons. The latter algorithm is also proved to be optimal in the worst case.