2026-09-08T01:21:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26422 2026-09-05T19:42:57Z ddc:004 open_access

Visibility Queries in Simple Polygons Bhore, Sujoy Liu, Chih-Hung Naredla, Anurag Murty Nekrich, Yakov Oh, Eunjin van Renssen, André Staals, Frank Wang, Haitao Xue, Jie simple polygons visibility polygons visibility queries polygon decompositions 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(n³) space. In this paper, we propose a new data structure that uses O(n^{2+ε}) space, for any ε > 0, while achieving the same query time. If only O(n²) space is available, the best known result provides O(log² n + k) query time. We improve this to O(log n log log n + k) time. When restricted to o(n²) 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(n^{1/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(log² n + k) query time; alternatively, we achieve O(log n + k) query time using O(n^{1+ε}) space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Chih-Hung Liu and Anurag Murty Naredla and Yakov Nekrich and Eunjin Oh and André van Renssen and Frank Staals and Haitao Wang and Jie Xue 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.33 urn:nbn:de:0030-drops-264222 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.33 eng https://creativecommons.org/licenses/by/4.0/legalcode