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.

Cell decomposition, Computational geometry, Data structure, Radial decomposition, Visibility
Theory of Computing Systems
School of Computer Science

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