2019

# Computing the k-crossing visibility region of a point in a polygon

## Publication

### Publication

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.

Additional Metadata | |
---|---|

Keywords | Computational geometry, Radial decomposition, Visibility |

Persistent URL | dx.doi.org/10.1007/978-3-030-25005-8_2 |

Series | Lecture Notes in Computer Science |

Citation |
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 |