arxiv: 2605.03334 · v1 · submitted 2026-05-05 · 💻 cs.CG · cs.DS

Recognition: unknown

Visibility Queries in Simple Polygons

Andr\'e van Renssen, Anurag Murty Naredla, Chih-Hung Liu, Eunjin Oh, Frank Staals, Haitao Wang, Jie Xue, Sujoy Bhore, Yakov Nekrich

Pith reviewed 2026-05-09 16:46 UTC · model grok-4.3

classification 💻 cs.CG cs.DS

keywords visibility queriessimple polygonsdata structurespolygon decompositionquery timespace complexitycomputational geometry

0 comments

The pith

Novel decomposition of simple polygons enables optimal visibility queries with O(n^{2+ε}) space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops data structures to answer visibility queries inside a simple polygon: given any point q, report the polygon visible from q. Prior work needed O(n^3) space to achieve the optimal O(log n + k) query time where k is the output size. The new approach reduces space to O(n^{2+ε}) while keeping the same query time, and supplies improved time-space trade-offs in other regimes including O(log n log log n + k) with quadratic space and sublinear time with near-linear space. A sympathetic reader would care because these bounds make preprocessing feasible for larger polygons arising in robotics, graphics, and geographic information systems.

Core claim

We present a data structure that preprocesses a simple polygon P with n vertices so that for any query point q inside P the visibility polygon of q can be reported in O(log n + k) time using O(n^{2+ε}) space for any ε > 0. This matches the best known query time but improves the space bound from the previous O(n^3). The result is obtained via a new decomposition method for simple polygons that may be of independent interest. We also give an O(n log n)-space structure with O(n^{1/2+ε} + k) query time and boundary-query variants that reach O(log n + k) with O(n^{1+ε}) space.

What carries the argument

A new decomposition method for simple polygons that partitions the interior to support efficient visibility reporting without cubic space overhead.

Load-bearing premise

The new decomposition method for simple polygons can be constructed and used to support the claimed space and query bounds without hidden logarithmic or polynomial factors that would change the asymptotics.

What would settle it

A concrete simple polygon on which the decomposition requires more than O(n^{2+ε}) space or on which any data structure built from it answers some visibility query in more than O(log n + k) time would falsify the central claim.

read the original abstract

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 \in 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^3)$ space. In this paper, we propose a new data structure that uses $O(n^{2+\epsilon})$ space, for any $\epsilon > 0$, while achieving the same query time. If only $O(n^2)$ space is available, the best known result provides $O(\log^2 n + k)$ query time. We improve this to $O(\log n \log \log n + k)$ time. When restricted to $o(n^2)$ 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+\epsilon} + 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^2 n + k)$ query time; alternatively, we achieve $O(\log n + k)$ query time using $O(n^{1+\epsilon})$ space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper improves space for optimal-time visibility queries in simple polygons from cubic to near-quadratic via a new decomposition.

read the letter

This paper improves space for optimal-time visibility queries in simple polygons from cubic to near-quadratic via a new decomposition. The headline result is an O(n^{2+ε}) space structure that still answers queries in O(log n + k) time. They also tighten the quadratic-space case to O(log n log log n + k) time, give an O(n log n) space option for O(n^{1/2+ε} + k) queries, and handle boundary points with either O(n log n) space and O(log² n + k) time or O(n^{1+ε}) space and O(log n + k) time. The new polygon decomposition is the enabling technique and looks like it could be useful on its own. The paper does well by laying out the full set of tradeoffs and directly comparing each one to the prior best bounds in the literature. The claims are stated with the right ε terms and no overstatement in the abstract. The soft spots are limited. The main one is that the decomposition construction and analysis need full verification to confirm there are no hidden polynomial or log factors that would change the asymptotics in practice. The stress-test found the high-level argument internally consistent with no contradictions, so this is a matter of checking details rather than a load-bearing gap. This work is for computational geometers who build or use visibility data structures, especially in robotics, graphics, or GIS. Anyone tracking the best known space-time curves for polygon queries will want the updated bounds. I would bring it to a reading group focused on geometric data structures. It deserves peer review because the improvements are concrete and the technique is new enough to merit detailed checking.

Referee Report

2 major / 2 minor

Summary. The paper studies data structures for visibility queries in a simple polygon P with n vertices: preprocess P so that, for any query point q in P, the visibility polygon of q can be reported in O(log n + k) time (k = output size). Prior work achieved this query time with O(n^3) space; the authors give a new decomposition of P that yields O(n^{2+ε}) space for any ε>0 while preserving the query time. They also improve the O(n^2)-space regime from O(log² n + k) to O(log n log log n + k), the o(n²)-space regime from O(n log n) space and O(k log n) time to O(n log n) space and O(n^{1/2+ε} + k) time, and give two trade-offs for the boundary-query special case.

Significance. If the new decomposition technique and its space/query analysis hold, the result improves the best known space for optimal-visibility-query time by roughly a linear factor and supplies a family of improved trade-offs across the space spectrum. The decomposition itself is presented as potentially reusable for other polygon problems. These are concrete, non-trivial advances in a core computational-geometry primitive.

major comments (2)

[§4] §4 (Decomposition construction): the space bound O(n^{2+ε}) for the visibility data structure is derived from the size of the new decomposition; the analysis must explicitly bound the hidden factors in the construction time and the number of sub-polygons produced, because any extra polylog or n^δ term would alter the claimed exponent.
[§5.2] §5.2 (Query algorithm): the O(log n + k) query time relies on traversing a constant number of decomposition cells per output edge; the proof must show that the cell-to-cell navigation cost remains O(1) per edge even after the ε-approximation is introduced, otherwise the query time becomes O(log n + k + n^δ) for some δ>0.

minor comments (2)

The abstract and introduction state the four main results but do not include a single table summarizing the old vs. new space/query pairs; adding such a table would improve readability.
[§3] Notation for the decomposition (e.g., the parameter ε and the depth of recursion) is introduced in §3 but used without re-definition in later sections; a short notation table or consistent re-statement would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive evaluation of the significance of our results, and the recommendation for minor revision. The two major comments concern the explicitness of the analysis in the decomposition and query sections. We address each point below and will incorporate the requested clarifications into the revised manuscript.

read point-by-point responses

Referee: [§4] §4 (Decomposition construction): the space bound O(n^{2+ε}) for the visibility data structure is derived from the size of the new decomposition; the analysis must explicitly bound the hidden factors in the construction time and the number of sub-polygons produced, because any extra polylog or n^δ term would alter the claimed exponent.

Authors: We agree that the analysis in §4 must make all factors explicit to confirm that the O(n^{2+ε}) space bound holds without hidden n^δ or super-polylogarithmic terms. In the revised version we will add a dedicated lemma that bounds the number of sub-polygons produced by the decomposition by O_ε(n^{2+ε}) and shows that the construction time is O(n^{2+ε} polylog n) with the polylog factor independent of ε. The proof will track the constants arising from the ε-approximations and the recursive partitioning, ensuring no additional polynomial factors are introduced. revision: yes
Referee: [§5.2] §5.2 (Query algorithm): the O(log n + k) query time relies on traversing a constant number of decomposition cells per output edge; the proof must show that the cell-to-cell navigation cost remains O(1) per edge even after the ε-approximation is introduced, otherwise the query time becomes O(log n + k + n^δ) for some δ>0.

Authors: We concur that the query-time analysis in §5.2 must explicitly verify that the per-edge navigation cost stays O(1) after the ε-approximations. In the revision we will insert a short lemma proving that each output edge is charged to a constant number of decomposition cells whose boundaries can be traversed in amortized O(1) time using the precomputed pointers and the ε-approximate windows; the total overhead therefore remains absorbed into the O(log n + k) bound. The argument relies on the fact that the approximation affects only the window sizes, not the number of cells crossed per edge. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central contribution is a new decomposition technique for simple polygons that enables the stated space-query tradeoffs (O(n^{2+ε}) space for O(log n + k) queries, etc.). No load-bearing step in the abstract or high-level description reduces a claimed result to a fitted parameter, self-citation chain, or definitional tautology. The derivation is presented as resting on an independent algorithmic construction rather than re-deriving prior quantities by construction. This is the expected honest non-finding for a computational geometry data-structure paper whose improvements are not statistically forced from the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Results rest on a new polygon decomposition whose correctness is not detailed in the abstract. No explicit free parameters or invented entities are mentioned. Standard computational-geometry assumptions (simple polygon, general position) are implicitly used.

axioms (1)

domain assumption The input is a simple polygon with n vertices.
Stated in the problem definition; required for all visibility results in the abstract.

pith-pipeline@v0.9.0 · 5661 in / 1137 out tokens · 44105 ms · 2026-05-09T16:46:57.667784+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Agarwal and Micha Sharir

1 Pankaj K. Agarwal and Micha Sharir. Ray shooting amidst convex polygons in 2D.Journal of Algorithms, 21(3):508–519, 1996.doi:10.1006/jagm.1996.0056. 2 Boris Aronov, Leonidas J. Guibas, Marek Teichmann, and Li Zhang. Visibility queries and maintenance in simple polygons.Discrete and Computational Geometry, 27(4):461–483,

work page doi:10.1006/jagm.1996.0056 1996
[2]

Ray shooting in polygons using geodesic triangulations.Algorithmica, 12:54–68, 1994.doi:10.1007/BF01377183

Hershberger, Micha Sharir, and Jack Snoeyink. Ray shooting in polygons using geodesic triangulations.Algorithmica, 12:54–68, 1994.doi:10.1007/BF01377183. 10 Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geometry.Discrete and Computational Geometry, 4:551–589, 1989. doi:10.1007/BF02187747. 11 Danny Z. Chen and Ovidi...

work page doi:10.1007/bf01377183 1994
[2]

3 Prosenjit Bose, Anna Lubiw, and J

doi:10.1007/s00454-001-0089-9. 3 Prosenjit Bose, Anna Lubiw, and J. Ian Munro. Efficient visibility queries in simple polygons. Computational Geometry: Theory and Applications, 23(3):313–335,

work page doi:10.1007/s00454-001-0089-9
[3]

Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E

Bhore, Liu, Naredla, Nekrich, Oh, van Renssen, Staals, Wang, and Xue 37 18 Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons.Algorithmica, 2(1-4):209–233, 1987.doi:10.1007/BF01840360. 19 Leonidas J. Guibas, Rajeev Motw...

work page doi:10.1007/bf01840360 1987
[3]

5Timothy M

URL:https://www.cccg.ca/proceedings/2011/papers/paper95.pdf. 5Timothy M. Chan and Da Wei Zheng. Simplex range searching revisited: How to shave logs in multi-level data structures. InProceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1493–1511, 2023.doi:10.1137/1.9781611977554.ch54. 6 Bernard Chazelle. A theorem on poly...

work page doi:10.1137/1.9781611977554.ch54 2011
[4]

7 Bernard Chazelle

doi:10.1109/SFCS.1982.58. 7 Bernard Chazelle. Triangulating a simple polygon in linear time.Discrete and Computational Geometry, 6:485–524, 1991.doi:10.1007/BF02574703. 8 Bernard Chazelle. Cutting hyperplanes for divide-and-conquer.Discrete and Computational Geometry, 9:145–158, 1993.doi:10.1007/BF02189314. 9 Bernard Chazelle, Herbert Edelsbrunner, Michel...

work page doi:10.1109/sfcs.1982.58 1982
[5]

11 Danny Z

doi:10.1007/BF02187747. 11 Danny Z. Chen and Ovidiu Daescu. Maintaining visibility of a polygon with a moving point of view.Information Processing Letters, 65:269–275,

work page doi:10.1007/bf02187747
[6]

12 Danny Z

doi:10.1016/S0020-0190(97) 00211-1. 12 Danny Z. Chen and Haitao Wang. Visibility and ray shooting queries in polygonal domains. Computational Geometry: Theory and Applications, 48:31–41,

work page doi:10.1016/s0020-0190(97
[7]

Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, Ren´ e Sitters, and Thomas Wolle

doi:10.1016/j.comgeo. 2014.08.003. 13 Danny Z. Chen and Haitao Wang. Weak visibility queries of line segments in simple polygons. Computational Geometry: Theory and Applications, 48:443–452, 2015.doi:10.1016/j.comgeo. 2015.02.001. 14 James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent.Journal of Compu...

work page doi:10.1016/j.comgeo 2014
[8]

1989 , issn =

doi: 10.1016/0022-0000(89)90034-2. 15 Herbert Edelsbrunner, Leonidas J. Guibas, and Jorge Stolfi. Optimal point location in a monotone subdivision.SIAM Journal on Computing, 15(2):317–340,

work page doi:10.1016/0022-0000(89)90034-2
[9]

17 Leonidas J

doi:10.1016/0196-6774(81) 90019-5. 17 Leonidas J. Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126–152,

work page doi:10.1016/0196-6774(81
[10]

Bhore, Liu, Naredla, Nekrich, Oh, van Renssen, Staals, Wang, and Xue 37 18 Leonidas J

doi:10.1016/0022-0000(89) 90041-X. Bhore, Liu, Naredla, Nekrich, Oh, van Renssen, Staals, Wang, and Xue 37 18 Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons.Algorithmica, 2(1-4):209–233, 1987.doi:10.1007/BF01840360....

work page doi:10.1016/0022-0000(89 1987
[11]

Kirkpatrick

22 David G. Kirkpatrick. Optimal search in planar subdivisions.SIAM Journal on Computing, 12(1):28–35, 1983.doi:10.1137/0212002. 23 Lin Lu, Chenglei Yang, and Jiaye Wang. Point visibility computing in polygons with holes.Journal of Information and Computational Science, 8(16):4165–4173,

work page doi:10.1137/0212002 1983
[12]

24 Ji˘ rí Matoušek

URL: https://www.researchgate.net/publication/282763094_Point_visibility_ computing_in_polygons_with_holes. 24 Ji˘ rí Matoušek. Efficient partition trees.Discrete and Computational Geometry, 8(3):315–334, 1992.doi:10.1007/BF02293051. 25 Michel Pocchiola. Graphics in flatland revisited. InProceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SW...

work page doi:10.1007/bf02293051 1992
[13]

doi: 10.1016/j.comgeo.2007.02.005

work page doi:10.1016/j.comgeo.2007.02.005 2007