CS Paper Radar

Best of Two Worlds: Combining High and Low Resolution to Compute Viewsheds on terrains

Laura Toma

cs.DS ·submitted 2026-10-01 02:17 UTC · v1
published

Abstract

The viewshed of a point $v$ on a grid terrain $T$, viewshed$_T(v)$, is defined as the set of grid points in $T$ that are visible from $v$. We describe a novel algorithm for computing viewshed$_T(v)$ using a multi-resolution approach: Given a parameter $k >1$ that represents the block size, we create a grid $T'$ which is a lower-resolution version of $T$, such that each point in $T'$ corresponds to a block of $\lceil \sqrt k \rceil $-by-$\lceil \sqrt k \rceil$ points in $T$. The key of our approach is using $T'$ to speed up the computation of viewshed$_T(v)$ while not introducing approximation. We compute viewshed$_T(v)$ in two steps: First we compute the viewshed of $v$ on $T'$, while maintaining the invariant that any block in $T'$ that is labeled as invisible may not contain any visible points. Thus, the first step's role is to use $T'$ to filter out blocks in $T$ that are guaranteed to be invisible. The second step considers the blocks that were labeled as visible in $T'$ and computes the visibility of their points with full accuracy using the data in $T$. Overall the algorithm runs in $O(n + \frac nk \lg \frac nk + k \lg k + l \cdot \lg n)$, where $l$ is the total size of visible blocks in $T'$. When $k = Ω(1)$ and $l = o(n) $, the running time of our algorithm improves on the previous best bound of $O(n \lg n)$. Our experimental results show the performance of the new algorithm in practice and a speedup of more than an order of magnitude compared to previous algorithms.

Comment
27 pages, 19 figures, short version appeared in Proc. ACM SIGSPATIAL GIS 2018

Closest papers

Nearest neighbours by meaning across the whole index.

Visibility on Terrains

cs.CY ·2026-09-30 ·Laura Toma
similarity 0.64
Abstract · 10 pages, 2 figures, chapter invited to the Encyclopedia of GIS

This chapter surveys terrain visibility models, algorithms, and applications. It introduces basic definitions, from line-of-sight, single-viewpoint viewsheds to cumulative and total viewsheds, on both Triangulated Irregular Network (TIN) and regular grid terrains. Reviews exact and approximate algorithms and highlights key application domains including archaeology, visual exposure to greenery, scenic route management, and land conservation.

0.31

Efficient K-Visibility Query in Polygons

cs.CG ·2026-09-01 ·Yeganeh Bahoo, Roni Sherman
publishedtheory similarity 0.63
Abstract · To appear in Proceedings of ALGOWIN 2026

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.

0.31

Hypergeometric Bridges for Multidimensional Grid Visibility

cs.CG ·2026-10-12 ·Ibrahim Ibrahim, Wilm Decré
theory similarity 0.61
Abstract · 24 pages, 8 figures, 3 tables

Established interpolation-based methods efficiently compute visibility from one source to every grid cell using values computed closer to the source. Interpolation yields fractional values even on binary grids of free or fully blocking cells. Two-dimensional path-counting theory interprets these values as fractions of unobstructed grid paths, but three-dimensional methods use different predecessor structures. Interpreting these values consistently across dimensions and on nonbinary grids remains unresolved. We provide a unified mathematical account that gives every visibility value a precise meaning in any dimension. We establish when grid refinement yields eventual agreement with continuous visibility, implement parallel solvers, and compare four three-dimensional methods in accuracy and throughput. We define cell transmission: zero blocks visibility, one preserves it, and intermediate values attenuate it proportionally. We prove each computed value equals the uniform finite-path average of transmission products over finitely many source-to-cell grid paths. It is the fraction of clear paths on binary grids and the mean path transmission on nonbinary grids. For a source--target query, the fractions of paths passing through cells at each step form a hypergeometric distribution in 2D, which we call the hypergeometric bridge. On the last step into the target, these probabilities equal the interpolation weights. Higher-dimensional interpolation weights arise from products of hypergeometric bridges. For any fixed dimension, the full-field algorithm remains linear in grid size. Exact path enumeration reproduces every checked visibility value. NumPy, OpenMP, and CUDA agree numerically, and our OpenMP solver achieves the highest throughput in the four-method CPU comparison at every tested resolution.

0.27

Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable

cs.CG cs.DMcs.DS ·2026-09-21 ·Udvas Das, Shouvik Mondal, Sasanka Roy
theory similarity 0.59
Abstract

In the classical Art Gallery Problem (AGP), guards are placed in a polygon so that together they see every point. The Witness Set Problem (WSP), introduced by Amit, Mitchell, and Packer, is a natural dual to the AGP. In this paper, we study the WSP in weak visibility polygons (WVPs), the simple polygons in which every point is seen from some point of one fixed edge. A witness set is a set of points whose visibility regions are pairwise disjoint, so that no single guard sees two of them. A maximum witness set, therefore, lower-bounds the guard number. Exact polynomial-time algorithms for the WSP are known only for monotone mountains, a proper subclass of WVPs. We give the first exact polynomial-time algorithms for the WSP in WVPs, in two settings. In the Discrete Witness Set Problem (DiscWSP), the witnesses come from a given set of $m$ points, and we find a maximum witness subset in $O(n + m \log(n+m))$ time on an $n$-vertex polygon. The algorithm rests on a structural fact: the visibility intersection graph of a WVP, in which two points are adjacent if their visibility regions intersect, is a trapezoid graph, that is, an intersection graph of trapezoids between two parallel lines. Moreover, the class of these graphs properly contains the interval graphs and the permutation graphs, which may be of independent interest in graph theory. We also prove an $Ω(n \log n)$ lower bound in the algebraic decision-tree model for instances with $m = Θ(n)$, so our algorithm for DiscWSP is optimum. In the Continuous Witness Set Problem (ContWSP), a witness may be any point of the polygon, and we give an exact algorithm running in $O(n \log n + ρ^{2}(n + ρ^{2}))$ time, where $ρ$ is the number of reflex vertices.

0.13

Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable

cs.CC cs.DS ·2026-09-29 ·Yuxuan Zhou
similarity 0.56
Abstract

We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids $P_k\square P_n$ with at most three colors. For every fixed height $k$, it computes the minimum number of moves and an optimal sequence in $N^{O(k^2)}$ time, where $N=kn$. This resolves the previously open three-color case on complete $3\times n$ boards. The proof uses a representation of flooding strategies as paintings by connected regions. We show that an optimal painting can be chosen so that its regions form a rooted tree with strong restrictions on the colors along ancestral paths. These restrictions make the part of the tree visible in any fixed-size connected window admit only polynomially many descriptions. The remaining common ancestors may form an arbitrarily long chain. We retain that chain on a stack and use a finite context-free recurrence to minimize the total painting cost without enumerating all possible stack contents. Connectivity information at the boundary ensures that the resulting local descriptions assemble into one valid global painting. The argument also applies to graphs supplied with an ordering into connected layers of bounded size, provided every edge lies within one layer or joins consecutive layers. A family of three-row boards shows that the unbounded ancestor chains handled by the algorithm are necessary even for optimal paintings. For any fixed height and palette size, we also give a deterministic EPTAS and a randomized sampling variant with an explicit failure-probability bound. These approximation results use a separate algorithm with single-exponential dependence on the move budget.

0.17

Fast Geometric Spanners via Approximate Nearest Neighbor Search

cs.DS cs.CG ·2026-09-22 ·Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang
similarity 0.56
Abstract

We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search. In particular, we show the following results for any metric space $\mathsf{M} = ([n], \mathsf{d})$ with aspect ratio $Δ$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime $τ_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k \in \mathbb{N}$, constructs an $O(c k)$-distortion spanner with $\tilde{O}(kn^{1+1/2k} \log Δ)$ edges and runs in time $\tilde{O}(τ_{\mathsf{M}} \cdot k n^{1/k} \log Δ)$. (2) Any algorithm that learns at most $o(n^{1+1/k}/k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $Ω(c k)$ distortion. Our results entail that (truly) sub-quadratic time algorithms for spanner construction is equivalent to subquadratic time BANN (up to constant-factor losses). As a further application, we use our fast spanner constructions to obtain a fast algorithm for approximating the Wasserstein distance $\mathsf{W}_q$, for all $q > 1$, over any metric space admitting an efficient batch approximate nearest neighbor search algorithm. Together with recent new efficient algorithms for approximate nearest neighbor search in $\ell_p$ spaces, for $p > 2$, our results entail the first subquadratic time algorithms for spanner construction (with the stated size-distortion tradeoff) and $\mathsf{W}_q$ distance approximation over these metric spaces.

0.07

Optimal Planar $k$ Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics

cs.CG ·2026-10-12 ·Chih-Hung Liu
top venuetheory similarity 0.55
Abstract · 78 pages. A conference version will appear in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

0.42

Two-point Approximate Shortest Path Queries among Convex Polygonal Obstacles in the Plane

cs.CG ·2026-08-10 ·Siddharth Gaur, R. Inkulu
similarity 0.55
Abstract

Given a polygonal domain $\cal P$ consisting $h$ pairwise disjoint convex polygonal obstacles together defined with $n$ vertices and a positive real number $ε$ in $(0, 0.6)$, this paper presents an algorithm to preprocess $\cal P$ in $O(n+\frac{h}ε(h+\frac{1}{\sqrtε})\lg(\frac{h}{\sqrtε}))$ time to compute data structures of size $O(n+\frac{h}{\sqrtε} (h+\frac{1}ε))$ so that given any two points $s$ and $t$ in the free space defined by $\cal P$, a path between $s$ and $t$ with a $(1+ε)$ multiplicative stretch and $13\ell$ additive stretch is output in $O(\frac{1}{\sqrtε}(\lg{\frac{h}{\sqrtε}})+\frac{h}{ε^{2.5}}(\lg{\lg(\frac{h}{\sqrtε})}))$ time. Here, $\ell$ is upper bounded by $(\sqrt{2ε}) (\max_{P_i \in \cal P} \max_{p, q \in P_i} |pq|)$.

0.04