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

arXiv: https://arxiv.org/abs/1803.10184 · HTML: https://mlsanity.com/paper/1803.10184/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2018.

## Built on by (most cited first, 2 of 2)

- [Minimizing Turns in Watchman Robot Navigation: Strategies and Solutions](https://mlsanity.com/paper/2308.10090/) (2023)
- [Securing Pathways with Orthogonal Robots](https://mlsanity.com/paper/2308.10093/) (2023)

## Abstract (arXiv)

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(√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.