arXiv preprint ·

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

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

Published
Source
arXiv preprint, posted before peer review
Original
Read it at arXiv
Topics
Dynamical SystemsStatistical MechanicsComputational GeometryData Analysis & Statistics

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Dynamical Systems

Get the few papers worth your time in Dynamical Systems every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics