Computing the k-Visibility Region of a Point in a Polygon
Two points p and q in a simple polygon P are k-visible when the line segment pq crosses the boundary of P at most k times. Given a query point q, a positive integer k, and a polygon P, we design an algorithm that computes the region of P that is k-visible from q in O(nk) time, where n denotes the number of vertices of P. This region is called the k-visibility region of q. This is the first algorithm parameterized in terms of k, resulting in an asymptotically faster worst-case running time compared to previous algorithms when k is o(log n) , and bridging the gap between the O(n)-time algorithm for computing the 0-visibility region of q in P and the O(nlog n) -time algorithm for computing the k-visibility region of q in P for any k. We also design a data structure of size O(n5) that supports visibility queries, returning the k-visible region of P for any arbitrary query point q in O(log n+ m) time, where m denotes the number of vertices on the boundary of the output visibility region.
|Keywords||Cell decomposition, Computational geometry, Data structure, Radial decomposition, Visibility|
|Journal||Theory of Computing Systems|
Bahoo, Y. (Yeganeh), Bose, P, Durocher, S. (Stephane), & Shermer, T.C. (Thomas C.). (2020). Computing the k-Visibility Region of a Point in a Polygon. Theory of Computing Systems. doi:10.1007/s00224-020-09999-0