PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient K-Visibility Query in Polygons

Yeganeh Bahoo, Roni Sherman

arXiv:2609.01472v1cs.CG

TL;DR

Existing k-visibility query structures lack a tight cell decomposition that removes redundant boundaries while preserving visibility changes. This paper identifies primary horizon and secondary hinge lines, proving a Θ(n^4)-cell decomposition with O(n^4) storage and O(log n + m) query reconstruction.

  • Problem

    A tight minimal cell decomposition for k-visibility remains unresolved because all-vertex line arrangements introduce redundant boundaries and require O(n^5) space.

  • Method

    The framework classifies primary vertex horizons and secondary mutually critical hinge lines, then stores cell visibility sequences using delta-compressed arrangement-tree updates.

  • Results

    O(n^4) storage supports optimal O(log n + m) query reconstruction over a tight Θ(n^4)-cell decomposition with invariant combinatorial visibility structure.

  • Takeaways & Limitations

    Primary horizon and secondary hinge lines characterize the spatial boundaries where the combinatorial structure of k-visibility changes.

  • Takeaways & Limitations

    The framework assumes general position, including that no three polygon vertices are collinear.

Abstract

from arXiv · show

This paper investigates $k$-visibility, where a line of sight can penetrate up to $k$ obstacles. While computing the $k$-visibility polygon from a single query point is well-studied, existing spatial preprocessing approaches rely on full $O(n^2)$ line arrangements through all vertex pairs without characterizing the minimal set of topological boundaries. We present a refined cell decomposition framework that isolates the exact geometric events governing $k$-visibility: primary vertex horizon lines and secondary mutually critical hinge lines. We prove that this minimal set of partition lines yields a spatial decomposition of $Θ(n^4)$ cells within which the combinatorial structure of the $k$-visibility polygon remains strictly invariant. By leveraging a combinatorial $δ$-compression scheme across cell boundaries, we achieve an overall storage complexity of $\mathcal{O}(n^4)$ while supporting optimal $\mathcal{O}(\log n + m)$ query time to reconstruct explicit $k$-visibility polygons of size $m$. Our framework naturally extends to polygons containing holes.

1 Introduction · 2 Problem Statement · 3 The Geometric Structure of the k-Visibility Polygon

The paper defines k-visibility queries through boundary-crossing depth and seeks a minimal spatial decomposition preserving the combinatorial k-visibility polygon within each cell. It identifies critical-vertex windows as the geometric events governing structure, achieving Θ(n^4) cells, O(n^4) space, and O(log n + m) query reconstruction.

  • 1 Introduction: k-visibility allows the open segment between two points to cross the polygon boundary at most k times, defining Visk(q, P) as the points visible from q under this limit.The parameter k represents visibility depth or the number of obstacle walls penetrated.
  • 1 Introduction: Existing methods include O(n^2), O(n log n), and parameterized algorithms for computing k-visibility polygons, while prior query structures motivate efficient spatial preprocessing.The paper also notes applications including wireless k-modem illumination, indoor mapping, path-planning, and M-guarding.
  • 1 Introduction: O(n^5) space was required by a prior static k-visibility structure based on extending lines through all vertex pairs, producing redundant boundaries and an oversized arrangement.The arrangement has O(n^4) cells, including spurious boundaries where visibility does not change.
  • 1 Introduction: The proposed framework uses minimal primary and secondary horizon lines to construct Θ(n^4) cells without redundant lines, reducing storage from O(n^5) to O(n^4).A delta-compressed dual arrangement tree stores only O(1) atomic mutations along tree edges and supports O(log n + m) query reconstruction.
  • 2 Problem Statement: The preprocessing phase constructs D(P, k), a cell decomposition in which the combinatorial k-visible region remains invariant throughout each cell.The problem is posed for a simple polygon with n vertices and fixed non-negative integer k.
  • 2 Problem Statement: The query phase locates q’s cell and retrieves its k-visibility polygon Visk(q) from the preprocessed structure.The formulation assumes general position and excludes any three collinear vertices.
  • 3 The Geometric Structure of the k-Visibility Polygon: A k-visibility polygon boundary consists of k-visible boundary chains and visibility windows connecting disconnected visible chains.Chains may lie on the polygon boundary or its bounding box and have visibility depth k from q.
  • 3 The Geometric Structure of the k-Visibility Polygon: Each visibility window is generated by one critical vertex and is characterized by that vertex, a proximal edge, and a distal edge, separating visible and occluded regions.A critical vertex has both incident edges strictly on one side of the line through the vertex and the reference point.

4 Combinatorial Cell Data and Storage Representation · 5 Spatial Partition Lines: Classification and Correctness

The framework stores an invariant combinatorial visibility sequence per spatial cell and reconstructs exact geometry dynamically at query time. The decomposition uses necessary primary horizon and secondary hinge lines to isolate every topological mutation while excluding noncritical horizons.

  • 4 Combinatorial Cell Data and Storage Representation: Exact visibility boundaries are reconstructed dynamically by shooting rays from q through each critical vertex to its proximal and distal edges.The stored sequence remains topologically fixed, while window endpoint coordinates are recomputed for the query point.
  • 4 Combinatorial Cell Data and Storage Representation: Each cell stores an invariant counter-clockwise combinatorial sequence of k-visible vertices and window generator tuples.Window tuples encode a critical vertex with proximal and distal edges.
  • 5 Spatial Partition Lines: Classification and Correctness: The partition overlays primary horizon lines from Visk(v) and Visk−2(v), plus secondary hinge transition lines generated by mutually critical vertices.These lines are classified as Type 1a, Type 1b, and Type 2 visibility-event boundaries.
  • 5 Spatial Partition Lines: Classification and Correctness: Type 1a horizons are mandatory because crossing them changes a vertex’s sequence status and can update a window’s distal-edge descriptor.The theorem requires these boundaries for every vertex’s Visk(v) window extensions.
  • 5 Spatial Partition Lines: Classification and Correctness: Type 1b horizons are necessary because crossing them moves a vertex into the visibility interior and changes the recorded proximal-edge descriptor.The corresponding windows derive from Visk−2(v).
  • 5 Spatial Partition Lines: Classification and Correctness: Horizon lines from Visx(v) for x ≤ k−4 or x ≥ k+2 are unnecessary when v is not critical to the responsible vertex’s window.The paper states this as Theorem 3.
  • 5 Spatial Partition Lines: Classification and Correctness: Type 2 hinge lines are mandatory because crossing a mutually critical pair’s line swaps window-generator anchors, producing distinct stored sequences on opposite sides.The mutation applies across all valid mutually critical configurations, so the two query regions cannot share one topological cell.

6 Hinge Transition Lines

Hinge transition lines are determined by how the k-visibility polygon changes when the query point crosses the line through two mutually critical vertices. Eight generic cases and four adjacent-vertex cases exhaust the relevant secondary topological events, with partition lines required only for specified visibility-depth configurations.

  • Hinge transition criteria: Mutually critical vertices define a candidate line ℓg, and hinge transitions are identified by comparing visibility behavior on opposite sides of points x1 and x2.The analysis also defines shadows outside the polygon, unlike the cited prior work.
  • Case completeness: 12 cases exhaust the analysis: 8 generic subcases plus 4 adjacent-vertex special cases whose visibility behavior differs from the generic cases.The generic cases combine convex or reflex vertex types with same- or opposite-side configurations.
  • Event separation: The general-position assumption prevents three vertices from being collinear, while single-vertex critical events remain governed by primary horizon lines.Thus, hinge lines address secondary events rather than duplicating primary horizon-line boundaries.
  • Required partition lines: A partition line at x1x2 is necessary when Z = k −1, W = k, Z = k −3, W = k −2 or W = k −4.These configurations cause visibility-window mutations or changes in the stored window generator tuple as the query point crosses ℓg.

7 Algorithm: Constructing the Cell Decomposition

Algorithm 1 constructs the planar cell decomposition from primary horizon and hinge transition lines, then assigns each cell a permanent invariant visibility sequence. It processes representative points by traversing k-labeled boundary chains and recording visible vertices or visibility-window descriptors.

  • Algorithm specification: The preprocessing algorithm requires a simple polygon P with n vertices and threshold k ≥0, producing an arrangement whose cells store counter-clockwise sequences.Each cell Ci stores a sequence Si.
  • Arrangement Geometry Construction: Phase 1 collects primary horizon lines and hinge transition lines, removes duplicates, constructs their planar arrangement, and convexifies non-convex cells.Hinge lines arise from mutually critical vertex pairs; reflex-vertex edges are extended to split non-convex cells.
  • Combinatorial Sequence Propagation: Phase 2 samples an arbitrary representative point q in each cell, labels the polygon boundary, identifies visibility windows, and initializes the cell sequence.The sequence is initialized as Si ←∅ before boundary-chain traversal.
  • Combinatorial Sequence Propagation: During counter-clockwise traversal, each k-visible vertex is added directly to Si, while each visibility window contributes a descriptor containing its critical generator and ordered proximal and distal edges.The edge order is determined by which edge, eprox or edist, is encountered first.

8 Extension to Polygons with Holes · 9 Query Processing and Visibility Reconstruction

For polygons with holes, k-visibility querying extends by shooting rays through critical vertices, labeling visible chains, and connecting them with windows. Query processing locates q in O(log n) time, retrieves an invariant sequence, and reconstructs the explicit visibility polygon in linear time.

  • 8 Extension to Polygons with Holes: Critical-vertex rays extend single-point k-visibility computation from simple polygons to polygons with holes.The method shoots rays from the query point through critical vertices and labels the resulting polygonal chains with their k-visibility values.
  • 8 Extension to Polygons with Holes: Visible chains are traversed and connected with windows to form the k-visibility polygon.
  • 9 Query Processing and Visibility Reconstruction: O(log n) point location followed by linear-time boundary construction dynamically reconstructs Visk(q) for a query point q.
  • 9 Query Processing and Visibility Reconstruction: The arrangement identifies q’s unique cell, after which the procedure retrieves its invariant visibility sequence Si.Boundary reconstruction performs a single linear traversal over Si and maps its entries to physical coordinates.
  • 9 Query Processing and Visibility Reconstruction: O(|Si|) = O(n) time outputs the explicit geometry by connecting calculated vertices and boundary segments in Si order.
  • 9 Query Processing and Visibility Reconstruction: Standalone k-visible vertices in Si are connected directly to the evolving visibility-polygon boundary chain.
  • 9 Query Processing and Visibility Reconstruction: Window generator tuples encode two boundary edges, whose physical endpoints are obtained by intersecting the query-to-critical-vertex line with those edges.

10 Complexity of the Cell Decomposition … 13 Conclusion and Future Work

The framework partitions the polygon into Θ(n^4) cells with invariant visibility structure, then combines optimal output-sensitive queries with delta compression to reduce storage from O(n^5) to O(n^4). Its construction is based on primary vertex horizons and secondary hinge transition lines governing topological mutations.

  • 10 Complexity of the Cell Decomposition: Θ(n^4) spatial cells arise from intersections among O(n^2) primary visibility-window and secondary hinge-transition partition lines, independently of k.The boundaries capture the geometric events governing the decomposition.
  • 10 Complexity of the Cell Decomposition: O(n^5) space results from storing up to O(n) visibility-sequence vertices and window-generator tuples in each of the Θ(n^4) cells.This is the naive per-cell storage footprint.
  • 11 Complexity of the Query Phase: O(log n + m) query time reconstructs the explicit k-visibility polygon, where m = |S_i| and m is bounded by O(n).The query separates cell identification from geometric reconstruction.
  • 11 Complexity of the Query Phase: O(log n) time locates the unique arrangement cell containing the dynamic query point, after which its linked combinatorial visibility sequence is retrieved without extra overhead.Standard hierarchical or trapezoidal point-location methods provide the location step.
  • 12 Delta-Compressed Dual Arrangement Tree: A BFS spanning tree of the dual cell graph stores one full root sequence and compound edge deltas that transform each parent sequence into its child sequence.Compound deltas can encode simultaneous local mutations across a cell boundary.
  • 12 Delta-Compressed Dual Arrangement Tree: O(d) edit applications reconstruct the target visibility sequence by walking the unique tree path from the root cell, where d is the target cell’s depth.The atomic edits include REPLACE, INSERT, and DELETE operations.
  • 13 Conclusion and Future Work: O(n^4) space replaces the naive O(n^5) representation because the dual tree has O(n^4) edges, each storing a compound delta of size O(1).The framework classifies primary vertex horizons and secondary hinge transition lines from mutually critical vertex pairs as the exact mutation boundaries.

Appendix … B.2 CCO

The appendix analyzes when partition lines are redundant or necessary for k-visibility changes. It classifies mutually critical-vertex configurations and identifies the specific CCO parameter cases requiring partition lines.

  • A Redundancy of Windows of Visxv for x ≤k −4 and x ≥k + 2 (when v is not critical to the vertex responsible for the window): Under general position with no three collinear vertices, mutually critical configurations fall into three cases: reciprocal collinearity, one-way criticality, or no mutual criticality.These cases organize the redundancy analysis for visibility-window transitions.
  • A Redundancy of Windows of Visxv for x ≤k −4 and x ≥k + 2 (when v is not critical to the vertex responsible for the window): In Case 1, hinge transition lines handle the transition between two collinear mutually critical vertices.
  • A Redundancy of Windows of Visxv for x ≤k −4 and x ≥k + 2 (when v is not critical to the vertex responsible for the window): In Case 3, crossing the line through two non-mutually-critical vertices does not change whether v2 is visible or invisible.
  • A Redundancy of Windows of Visxv for x ≤k −4 and x ≥k + 2 (when v is not critical to the vertex responsible for the window): In Case 2, when v2 is non-critical and v1 is critical to it, a horizon line for x ≥k + 2 leaves v in shadow on both sides, so v does not enter or leave the visibility sequence.The same conclusion is illustrated for v2 under 4-visibility, where v2 remains entirely in shadow.
  • A Redundancy of Windows of Visxv for x ≤k −4 and x ≥k + 2 (when v is not critical to the vertex responsible for the window): For x ≤k −4, v remains completely within the visibility polygon on both sides of the horizon line and therefore does not change the visibility sequence.The 8-visibility example likewise keeps v2 within the visibility polygon at both query points.
  • B.2 CCO: A CCO partition line is needed for Z = k −1, W = k, Z = k −3, W = k −2, and W = k −4.These cases are associated with Figures 8–10.
  • B.2 CCO: For Z ≥k + 1 and W ≥k + 2, the relevant feature neighborhoods are entirely in shadow, while for Z ≤k −7 and W ≤k −6, they are entirely visible.The shadowed features are v2 and its immediate neighbourhood for Z, and x3x4 and its immediate neighbourhood for W.

C CRS · D CRO

The CRS and CRO analyses identify the parameter cases requiring partition lines and characterize when v2 or x3x4 neighborhoods are entirely shadowed or visible. Both sections use analogous threshold patterns, with CRO thresholds shifted relative to CRS.

  • C CRS: [C CRS] Partition lines are needed for CRS when Z = k, Z = k −2, W = k, Z = k −4, W = k −2, or W = k −4.These cases are illustrated in Figures 11–14.
  • C CRS: [C CRS] For Z ≥k + 2, v2 and its immediate neighbourhood are entirely in shadow, while for W ≥k + 4, x3x4 and its neighbourhood are entirely in shadow.For Z ≤k −8 and W ≤k −6, the corresponding neighborhoods are entirely visible.
  • C CRS: [C CRS] CRS examples cover Z = k with W = k + 2, through Z = k −6 with W = k −4.The intermediate configurations include Z = k −2, W = k and Z = k −4, W = k −2.
  • D CRO: [D CRO] Partition lines are needed for CRO when Z = k, Z = k −2, W = k, Z = k −4, W = k −2, or W = k −4.Lemma 4 states these cases and refers to Figures 15–19.
  • D CRO: [D CRO] For Z ≥k+4, v2 and its surroundings are entirely in shadow, while for W ≥k+6, x3x4 and its surroundings are entirely in shadow.For Z ≤k −8 and W ≤k −6, the corresponding neighborhoods are entirely visible.
  • D CRO: [D CRO] CRO examples range from Z = k + 2, W = k + 4 to Z = k −6, W = k −4.Figures 16–18 show the intermediate configurations Z = k, W = k + 2; Z = k −2, W = k; and Z = k −4, W = k −2.

E RCS · F RCO

E RCS and F RCO require partition lines at the same five boundary cases, while visibility or shadow becomes uniform beyond specified Z and W thresholds. The two sections present corresponding cases in Figures 20–22 and 23–25.

  • E RCS: E RCS requires partition lines when Z = k −1, W = k, Z = k −3, W = k −2, or W = k −4.These cases are illustrated in Figures 20–22.
  • E RCS: For E RCS, Z ≥k + 1 makes v2 and its surroundings entirely shadowed, while W ≥k + 2 does the same for x3x4 and its surroundings.The stated thresholds describe regions that no longer require additional visibility distinctions.
  • E RCS: For E RCS, Z ≤k −7 makes v2 and its surroundings entirely visible, while W ≤k −6 makes x3x4 and its surroundings entirely visible.These lower thresholds mark the corresponding fully visible configurations.
  • F RCO: F RCO requires partition lines in the same five cases: Z = k −1, W = k, Z = k −3, W = k −2, and W = k −4.Figures 23–25 depict these cases.
  • F RCO: For F RCO, Z ≥k + 1 places v2 and its surroundings entirely in shadow, while W ≥k + 2 places x3x4 and its surroundings entirely in shadow.The section states these upper-threshold configurations explicitly.
  • F RCO: For F RCO, Z ≤k−7 makes v2 and its surroundings entirely visible, while W ≤k−6 makes x3x4 and its surroundings entirely visible.These lower-threshold cases correspond to fully visible surroundings.

G RRS · H RRO

The G RRS and H RRO sections identify the same six cases requiring a partition line at x1x2, with visibility transitioning to complete shadow or visibility beyond specified Z and W thresholds.

  • G RRS: G RRS requires a partition line at x1x2 for six cases: Z = k, Z = k −2, W = k, Z = k −4, W = k −2, and W = k −4.These cases are illustrated in Figures 26–29.
  • G RRS: For G RRS, when Z ≤k−8, v2 and its surroundings are entirely visible, while W ≤k−6 makes x3x4 and its surroundings entirely visible.These thresholds complement the upper shadow conditions.
  • H RRO: For H RRO, when Z ≥k + 2, all of v2 is in shadow, while W ≥k + 4 makes x3x4 and its surroundings entirely in shadow.The section’s figures include the additional case Z = k −8, W = k −6.
  • H RRO: For H RRO, when Z ≤k −10, v2 and its surroundings are entirely visible, while W ≤k −8 makes x3x4 and its surroundings entirely visible.These lower thresholds follow the H RRO transition cases shown through Figure 34.

I RC-SC · J RR-SC · K CR-SC

The RC-SC, RR-SC, and CR-SC cases identify the parameter values requiring partition lines and specify thresholds where relevant regions become completely visible or invisible.

  • I RC-SC · J RR-SC · K CR-SC: Across all three configurations, partition lines occur at specific Z and W offsets from k, separating intermediate cases from fully visible or invisible regions.The supporting lemmas are Lemmas 9–11, with their proofs referring to the corresponding figures.
  • I RC-SC: RC-SC requires partition lines when Z = k, Z = k −2, W = k −1, or W = k −3.These cases correspond to Figures 35–37.
  • I RC-SC: For RC-SC, v2 is entirely in shadow when Z ≥k + 2, while x3x4 and its surroundings are entirely in shadow when W ≥k + 3.Conversely, v2 and x3x4 are entirely visible for Z ≤k −6 and W ≤k −5, respectively.
  • J RR-SC: RR-SC requires partition lines when Z = k, Z = k −2, W = k, or W = k −2.These cases are illustrated in Figures 38–40.
  • J RR-SC: For RR-SC, v2 and its surroundings are completely invisible when Z ≥k + 2, while x3x4 and its surroundings are completely invisible when W ≥k + 4.They are completely visible when Z ≤k −6 and W ≤k −4, respectively.
  • K CR-SC: CR-SC requires partition lines when Z = k −1, Z = k −3, W = k −1, or W = k −3.These cases are shown in Figures 41–43.
  • K CR-SC: For CR-SC, v2 and its surroundings are completely invisible when Z ≥k+1, while x3x4 and its surroundings are completely invisible when W ≥k+3.They are completely visible when Z ≤k −7 and W ≤k −5, respectively.

L CC-SC

The CC-SC case requires partition lines for specific combinations of Z and W relative to k. Outside these boundary ranges, the relevant features become completely invisible or completely visible.

  • L CC-SC: Partition lines are needed when Z = k −1, W = k, or W = k −2.These cases are illustrated in Figures 44–45.
  • L CC-SC: For Z ≥k + 1, v2 and its surroundings are completely invisible.
  • L CC-SC: For W ≥k + 2, x3x4 and its surroundings are completely invisible.
  • L CC-SC: For Z ≤k −5, v2 and its surroundings are completely visible, while for W ≤k −4, x3x4 and its surroundings are completely visible.
Loading 2609.01472v1…