An O(log N log log N) time RMESH algorithm for the simple polygon visibility problem

摘要

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.