Efficient Computation of Visibility Polygons

Abstract

Determining visibility in planar polygons and arrangements is an important subroutine for many algorithms in computational geometry. In this paper, we report on new implementations, and corresponding experimental evaluations, for two established and one novel algorithm for computing visibility polygons. These algorithms will be released to the public shortly, as a new package for the Computational Geometry Algorithms Library (CGAL).

Cited by in corpus (4)

• A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
• Engineering Art Galleries
• Motion Planning for Collision-resilient Mobile Robots in Obstacle-cluttered Unknown Environments with Risk Reward Trade-offs
• The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS