An O(log N log log N) time RMESH algorithm for the simple polygon visibility problem
Sung‐Ryul Kim, Kunsoo Park, Yookun Cho · Proceedings of the ... International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN) · 2002
In this paper we consider the simple polygon visibility problem: Given a simple polygon P with N vertices and a point z in the interior of the polygon, find all the boundary points of P that are visible from z. We present an O(logN loglogN) time algorithm that solves the simple polygon visibility problem on a /spl radic/N/spl times//spl radic/N RMESH. Previously, the best known algorithm for the problem on a /spl radic/N/spl times//spl radic/N RMESH takes O(log/sup 2/ N) time.>