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

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

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-13
DOI
https://doi.org/10.5281/zenodo.24183898
Primary Topic
Complex Systems and Time Series Analysis
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Francisco J. Muñoz, Juan Carlos Nuño
Zenodo (CERN European Organization for Nuclear Research)
Complex Systems and Time Series Analysis
preprint

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

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

Abstract

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

Zenodo (CERN European Organization for Nuclear Research)
Universidad Politécnica de Madrid (ES)
Complex Systems and Time Series Analysis
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon