An Optimal Algorithm for Computing the Visibility Area of a Polygon from a Point Using Constant-Memory
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 in P where only O(1) workspace is available. The problem was previously solved in O(cn) time, where c denotes the number of critical vertices for q which are the vertices of P where the visibility region changes. In another research, the visibility area of a point be computed in O(nr) time, where r denotes the cardinality of reflex vertices of P in the output. In this paper, we present an optimal algorithm of O(n) time, and O(1) space for computing visibility area. In the constant-memory model, so, we improve time-complexity of previous works such that it just depends on n . Actually, we provide a linear-time, constant-space, strict in-place and 2-pass algorithm for computing visibility area of a point inside a simple polygon, set of non-crossed line-segments and set of non-intersected simple polygons.
READ FULL TEXT