From point patterns to networks: to what extent does the Delaunay triangulation reproduce key spatial and density information?

Abstract To be used as an analysis tool, it is important that a spatial network’s construction algorithm reproduces the structural properties of the original physical embedding. One popular method for converting a two-dimensional (2D) point pattern into a spatial network is the Delaunay triangulation. Here, we apply the Delaunay triangulation to seven types of 2D point patterns, including hyperuniform systems (i.e. systems characterized by completely suppressed normalized infinite-wavelength density fluctuations). We demonstrate that the quartile coefficients of dispersion of multiple centrality measures are capable of rank-ordering hyperuniform and nonhyperuniform systems independently, but they cannot distinguish a nearly hyperuniform system from hyperuniform systems. Thus, in each system, we investigate the local densities of the point pattern $ \rho_{P}(\mathbf{r}_{i};\ell) $ and of the network $ \rho_{G}(n_{i};\ell) $. We reveal that there is a strong correlation between $ \rho_{P}(\mathbf{r}_{i};\ell) $ and $ \rho_{G}(n_{i};\ell) $ in nonhyperuniform systems but no such correlation in hyperuniform systems. Similarly, when calculating the pair-correlation function and local density covariance function on the point pattern and network, the point pattern and network functions are similar only in nonhyperuniform systems. In disordered (i.e. isotropic) hyperuniform systems, the network has a positive local density covariance at small distances; such covariance is not present in the corresponding point patterns. Thus, we demonstrate that the Delaunay triangulation accurately captures the density fluctuations of the underlying point pattern only when the point pattern possesses a positive local density covariance at small distances. Such positive correlation is seen in most real-world systems but is not seen in disordered hyperuniform systems. Generally, the Delaunay triangulation is an effective tool for building a spatial network from a 2D point pattern to reproduce the underlying density of the point pattern, but there are situations (i.e. disordered hyperuniform systems) where we caution that the Delaunay triangulation would not be effective at capturing the underlying physical embedding.