Computing a visibility polygon using few variables

2011/11/15 by Barba, Luis, Korman, Matias, Langerman, Stefan +1
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1111.3584

Abstract

We present several algorithms for computing the visibility polygon of a simple polygon P from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O(n\Rout) time, where \Rout denotes the number of reflex vertices of P that are part of the output. The next two algorithms use O(log \Rin) variables, and output the visibility polygon in O(nlog \Rin) randomized expected time or O(nlog² \Rin) deterministic time, where \Rin is the number of reflex vertices of P.

Related

• A New Optimal Algorithm for Computing the Visibility Area of a simple Polygon from a Viewpoint
• Space-efficient Algorithms for Visibility Problems in Simple Polygon
• Efficient Computation of Visibility Polygons
• Dynamic algorithms for visibility polygons in simple polygons
• Weak Visibility Queries of Line Segments in Simple Polygons