2012/12/25 by Danny Z. Chen, Haitao Wang, Chen, Danny Z. +1
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.1212.6039
openalex publication_date 2012/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a simple polygon P in the plane, we present new algorithms and data structures for computing the weak visibility polygon from any query line segment in P. We build a data structure in O(n) time and O(n) space that can compute the visibility polygon for any query line segment s in O(k log n) time, where k is the size of the visibility polygon of s and n is the number of vertices of P. Alternatively, we build a data structure in O(n3) time and O(n3) space that can compute the visibility polygon for any query line segment in O(k + log n) time.