A New Optimal Algorithm for Computing the Visibility Area of a simple Polygon from a Viewpoint
share
Given a simple polygon P of n vertices in the Plane. We study the problem of computing the visibility polygon from a given viewpoint q inside P where only few working variables can be used. The problem was previously solved in O(nr) time using O(1) variables for working space, where r denotes the cardinality of reflex vertices of P in the output. In this paper, we present an optimal in-place algorithm of O(n) time, and O(1) extra variables (in addition to the being in-place) for computing visibility area. If reporting the parts of P that are not in the visibility area is acceptable as result, our algorithm can be a constant-memory for computing visibility area. We improve time-complexity such that it just depends on n . Actually, we provide a linear-time and in-place algorithm for computing visibility area of a viewpoint inside a simple polygon.
READ FULL TEXT