A New Optimal Algorithm for Computing the Visibility Area of a simple Polygon from a Viewpoint

Abstract

Given a simple polygon $\mathcal{P}$ of $n$ vertices in the Plane. We study the problem of computing the visibility area from a given viewpoint $q$ inside $\mathcal{P}$ where only sub-linear variables are allowed for working space. Without any memory-constrained, this problem was previously solved in $O(n)$-time and $O(n)$-variables space. In a newer research, the visibility area of a point be computed in $O(n)$-time, using $O(\sqrt{n})$ variables for working space. In this paper, we present an optimal-time algorithm, using $O(c/\log n)$ variables space for computing visibility area, where $c<n$ is the number of critical vertices. We keep the algorithm in the linear-time and reduce space as much as possible.

5 pages, 3 figures