Efficient algorithm for finding the visibility polygon for a polygonal region with holes
哲夫 浅野, Tetsuo Asano · Institutional Repositories DataBase (IRDB) · 1985
We are given a polygonal region P with holes and one point q is specified in the region. The problem is how fast we can find the portion of the boundary of P that is visible from q. For this problem an efficient algorithm is presented which runs in time O(n log h) in the worst case and in time O(n plus h log h) if every hole is a convex polygon, where n is the total number of vertices of P and h is the number of holes.