β Scribed by Suri, S; O'Rourke, J
No coin nor oath required. For personal study only.
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.
π SIMILAR VOLUMES
Gautam Das q t Giri NarasimhanΓ bstract Let G = (V, 1?) be a n-vertex connected graph with positive edge weights. A subgraph G' is a t-spanner if for all u, v c V, the distance between u and v in the subgraph is at most t times the corresponding distance in G. We design an O(n log2 n) time algorithm