2026/05/05 by Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla +6 · 1 voice
Computer Science · #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.2605.03334
Given a simple polygon P with n vertices, we consider the problem of constructing a data structure for visibility queries: for any query point q ∈ P, compute the visibility polygon of q in P. To obtain O(log n + k) query time, where k is the size of the visibility polygon of q, the previous best result requires O(n3) space. In this paper, we propose a new data structure that uses O(n2+ε) space, for any ε> 0, while achieving the same query time. If only O(n2) space is available, the best known result provides O(log2 n + k) query time. We improve this to O(log n log log n + k) time. When restricted to o(n2) space, the only previously known approach, aside from the O(n)-time algorithm that computes the visibility polygon without preprocessing, is an O(n)-space data structure that supports O(k log n)-time queries. We construct a data structure using O(n log n) space that answers visibility queries in O(n1/2+ε + k) time. In addition, for the special case in which q lies on the boundary of P, we build a data structure of O(n log n) space supporting O(log2 n + k) query time; alternatively, we achieve O(log n + k) query time using O(n1+ε) space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.