CS Paper Radar

Visibility graphs of irregularly sampled two-dimensional fields via Voronoi tessellations

Francisco J. Muñoz, Juan Carlos Nuño

cs.CG math.DScond-mat.stat-mechphysics.data-an ·submitted 2026-11-12 05:58 UTC · v1

Abstract

Visibility graphs map a time series into a network by linking two data whenever the straight line between them is not obstructed by intermediate data. Their extension to two-dimensional fields has so far been restricted to regular lattices, where visibility is checked along a finite number of lattice directions. We propose a definition for scalar data sampled at arbitrary, irregularly scattered points of the plane. Each point is assigned its Voronoi cell, so that the data become a landscape of prisms, and two points are linked when the line of sight between them clears the cells crossed by the connecting segment. This yields horizontal ($\HVGV$) and natural ($\NVGV$) Voronoi visibility graphs that reduce exactly to the classical horizontal and natural visibility graphs when the points are collinear, contain the Gabriel graph of the point set, and can be built by an exact walk through the Delaunay triangulation. For uncorrelated heights, the horizontal graph depends only on the ranks of the data, so its statistics are independent of the marginal distribution. The probability that two points see each other is $2/[(M+1)(M+2)]$, where $M$ is the number of Voronoi cells crossed, which reduces the problem to the geometry of the tessellation. For Poisson points this gives a degree distribution with a scale-free tail $P(k)\simeq(π^3/4)\,k^{-2}$ and a mean degree that grows as $(π^3/8)\ln N$, in contrast with the finite value $\langle k\rangle=4$ of one-dimensional series. Two dimensions are therefore the marginal case in which isotropic horizontal visibility ceases to be local. Numerical simulations with up to $N=1.28\times10^5$ points support these predictions.

Comment
10 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Survey of Typical-Cell Volume Distributions in Poisson--Voronoi and Poisson--Delaunay Tessellations: Analytical Theory, High-Dimensional Limits, and Wireless Applications

cs.IT ·2026-08-12 ·Minghua Xia, Tian Shi, Wenkunn Wen
publishedsurvey similarity 0.62
Abstract · 23 pages, 3 figures, 3 tables, Accepted for publication in IEEE Access

Random spatial tessellations generated by point processes provide fundamental models for proximity, space partitioning, and local geometry in stochastic systems. Poisson--Voronoi and Poisson--Delaunay tessellations induced by homogeneous Poisson point processes form a canonical dual pair used in stochastic geometry, computational geometry, spatial statistics, and wireless-network analysis. Their typical-cell volume distributions provide important geometric inputs for modeling coverage, traffic load, clustering, connectivity, and other system characteristics. Despite extensive study, the literature remains analytically asymmetric. For Poisson--Voronoi cell volumes, exact integral representations exist in certain planar settings, while a recent scale--shape factorization provides an exact general-dimensional representation with conditional Gamma structure. However, the normalized shape laws and unbounded facet-count mixture remain implicit, and tractable unconditional closed-form distributions are unavailable. Practical modeling therefore relies largely on simulation, moment characterizations, and empirical approximations. By contrast, Poisson--Delaunay simplex volumes admit dimension-explicit PDFs, CDFs, and moment formulas derived through Mellin-transform analysis and Meijer's \(G\)-function representations. Motivated by this contrast, this paper surveys typical-cell volume distributions in Poisson--Voronoi and Poisson--Delaunay tessellations. We review the main analytical methods, synthesize exact and approximate results, summarize emerging high-dimensional limits, and discuss wireless-network applications, including load modeling, cooperative transmission, and three-dimensional architectures. We also identify open problems concerning unconditional Poisson--Voronoi distributions, non-Poisson spatial models, data-driven geometric inference, and dimension-aware network modeling.

0.62

A Collapse Process for Farthest Voronoi Diagrams of Lines in Three Dimensions

cs.CG ·2026-09-24 ·Evanthia Papadopoulou, Martin Suderland, Zeyu Wang
similarity 0.61
Abstract

We study a \emph{collapse process} to construct the farthest Voronoi diagram of lines in three dimensions, given a spherical map of the diagram's unbounded features. The collapse process sweeps through the diagram in order of decreasing distance from the farthest lines. It follows the \emph{shrinking map}, a cell complex on a topological sphere that encodes the locus of points with a fixed farthest distance. We show that, in three dimensions, the collapse process has exactly four non-terminal local event types that change the structure of the shrinking map: \emph{deletion, swap, local minimum}, and \emph{local maximum} events; plus one terminal event. This list is complete. We give intrinsic three-dimensional geometric descriptions of the four non-terminal events. First, we classify the two vertex-related events, deletion and swap events, by the spherical convex hull of the four tangent points from a vertex to its four defining lines. Then, we analyze the events related to the local extrema of the distance function along the trisector of three lines. We show that the distance function along a trisector has at most $4$ local maxima and $8$ local minima, and that both bounds are tight. The extrema can be found via a polynomial of degree $12$. As a byproduct, this gives a direct method for finding the smallest sphere tangent to three given lines. At each local extremum, the tangent sphere touches the three lines at points lying on a great circle. The collapse process and the completeness of the event list also apply, under similar general position assumptions, to the farthest Voronoi diagram of convex sites under strictly convex distance functions.

0.38

Visibility on Terrains

cs.CY ·2026-09-30 ·Laura Toma
similarity 0.60
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.59
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

Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications

cs.CG cs.DS ·2026-10-30 ·Bruce W. Brewer, Haitao Wang
top venue similarity 0.56
Abstract · To appear in SODA 2027

Let $P$ be a simple polygon with $m$ vertices. After $O(m)$-time preprocessing of $P$, for any set $S$ of $n$ additively weighted point sites, we compute an implicit additively weighted geodesic Voronoi diagram in $O(n\log n+n\log^2 m)$ time, supporting nearest-neighbor queries in $O(\log(n+m))$ time. In contrast, explicitly constructing the diagram requires $Ω(m)$ time. Our algorithm introduces a new sweep-line paradigm that avoids explicitly constructing the diagram, together with a novel technique for point location in implicit subdivisions. As applications, we obtain new dynamic data structures for additively weighted geodesic nearest-neighbor searching and the first efficient algorithms for shortest paths in geodesic disk graphs. After the same $O(m)$-time preprocessing, single-source shortest paths in a geodesic disk graph of $n$ sites can be computed in $O(n\log n+n\log^2 m)$ time in the unweighted case and $O(n^{3/2}(\log n+\log^2 m))$ time in the weighted case. We also extend our techniques to implicit farthest geodesic Voronoi diagrams for unweighted sites, obtaining analogous bounds and dynamic farthest-neighbor data structures.

0.47

VoroDuce: Massively Parallel 3D Voronoi Simplification with Volume-Aware Edge Collapse

cs.CG ·2026-10-15 ·Felix Windisch, Lukas Radl, Thomas Köhler, Shrisudhan Govindarajan, Marcel Pur +2 more
similarity 0.55
Abstract

3D Voronoi diagrams provide a powerful mathematical framework for representing volumetric functions and geometry with applications to Materials Science, Biology, Simulation and Astrophysics. However, accurately resolving fine structures often requires millions of cells, imposing severe computational and memory constraints. Traditional mesh decimation or point cloud simplification techniques fail to account for the effects re-meshing has on neighbouring cells. In this work, we formalize the Voronoi reduction problem and propose a greedy edge-collapsing algorithm on the dual Delaunay tetrahedralisation that accounts for changes in the local geometry. Further, we demonstrate a novel volumetric error approximation technique that models convex cell intersections as truncated prismatoids, circumventing computationally prohibitive exact volume calculations and enabling massive GPU parallelization. Evaluations across Synthetic, Medicine and Material Science data demonstrate that VoroDuce decimates models with up to a million primitives, successfully compressing the representation while preserving the underlying data better than naive decimation approaches.

0.20

CVTSplat: Multi-view Reconstruction Using an Adaptive Centroidal Voronoi Tessellation

cs.CV cs.GR ·2026-10-26 ·Briac Toussaint, Diego Thomas, Jean-Sébastien Franco, Edmond Boyer, Christian Theobalt
similarity 0.54
Abstract · 13 pages

Voronoi tessellations have recently emerged as an adaptive, space-partitioning discretization for shape and appearance reconstruction from multi-view images. However, the irregular cells they produce make the repeated reconstruction of the tessellation during optimization costly. We therefore explore adaptive centroidal Voronoi tessellations (CVTs), which extend standard CVTs with non-uniform cell sizes while preserving the regular, well-shaped cells that make them efficient to compute. In CVTSplat, cell size is modulated by the evolving signed distance field, concentrating sites near the zero level set while keeping cells nearly centroidal. This regularity lets us specialize the whole pipeline, with GPU algorithms for nearest-neighbor queries and approximate Voronoi construction, and a rasterizer tailored to small, nearly isotropic cells. Our Voronoi construction is 5 to 10 times faster than general-purpose alternatives in this regime. On DTU and BlendedMVS, CVTSplat reaches geometric accuracy competitive with the best Gaussian-splatting surface methods while training in about 2.5 minutes on a single GPU.

0.26

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

cs.DS ·2026-10-01 ·Laura Toma
published similarity 0.54
Abstract · 27 pages, 19 figures, short version appeared in Proc. ACM SIGSPATIAL GIS 2018

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.

0.46