Computing the k-crossing visibility region of a point in a polygon
Two points p and q in a simple polygon P are k-crossing visible when the line segment pq crosses the boundary of P at most k times. Given a query point q, an integer k, and a polygon P, we propose an algorithm that computes the region of P that is k-crossing visible from q in O(nk) time, where n denotes the number of vertices of P. This is the first such algorithm parameterized in terms of k, resulting in asymptotically faster worst-case running time relative 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(n log n)-time algorithm for computing the k-crossing visibility region of q in P.
|Keywords||Computational geometry, Radial decomposition, Visibility|
|Series||Lecture Notes in Computer Science|
Bahoo, Y. (Yeganeh), Bose, P, Durocher, S. (Stephane), & Shermer, T. (Thomas). (2019). Computing the k-crossing visibility region of a point in a polygon. In Lecture Notes in Computer Science. doi:10.1007/978-3-030-25005-8_2