Neighbours
This module contains neighbour search algorithms that can be applied to any tiling.
Note that certain construction kernels already built neighbourhood relation upon construction of the tiling or graph! Still, the general functions presented here, can be useful in a number of applications, such as spatial proximity search for refined or manipulated lattices, or in case a range of neighbours larger than immediately close cells is required.
Motivation
Computing adjacency relations in non-Euclidean tilings is challenging, especially for two-dimensional manifolds with negative curvature. These cannot be embedded into higher dimensional Euclidean spaces, making it difficult to establish a natural ordering for grouping or sorting cells by their position. Techniques like partitioning the Poincaré disk into rectangular grids, similar to hierarchical multigrid approaches, are hence ineffective. This is due to the manifold’s volume expanding exponentially in all directions, and the coordinate representation becoming significantly distorted near the boundary of the unit circle. Consequently, neither the Poincaré disk coordinates nor any higher-dimensional Euclidean-style grid system is suitable for efficient sorting.
Spatial proximity search
Given these difficulties, a conceptually straightforward way of identifying adjacent cells in any regular geometry is by radius search, which is available as a standalone function in the
neighbors
module and used as the default algorithm behind get_nbrs_list in some kernels, such as DUN07. However, it should be emphasized that any neighbor search method that
makes explicit use of Poincaré disk coordinates risks becoming inaccurate close to the unit circle, where the Euclidean distance between adjacent cells vanishes. For this reason, we recommend performing additional consistency checks whenever very large lattices are required. Compare our release publication for further information on adjacency in hyperbolic lattices.
We provide the following functions:
- hypertiling.neighbors.find_radius_brute_force(tiling, radius=None, eps=1e-05) List[List[int]]
Get adjacent polygons for the entire tiling through radius search This algorithm works in a brute-force manner, the distances between every pair of cells are compared against the search radius.
Time complexity: O(n^2) where n=len(tiling) Slow, use only for small tilings or for debugging purposes
Arguments:
- tilingsub-class of Tiling
The hyperbolic tiling object (represented by one of the “kernels”)
- radiusfloat
The search radius
- epsfloat
Add small value to search radius to avoid rounding issues
Returns:
List[List[int]] containing neighbour indices of every cell.
- hypertiling.neighbors.find_radius_optimized(tiling, radius=None, eps=1e-05) List[List[int]]
Get adjacent polygons for the entire tiling through radius search Compared to its brute-force equivalent, this improved implemention makes sure everything is fully vectorized and complied by numpy, such that we gain a dramatic speed-up
Time complexity: O(n^2) where n=len(tiling)
Arguments:
- tilingsub-class of Tiling
The hyperbolic tiling object (represented by one of the “kernels”)
- radiusfloat
The search radius
- epsfloat
Add small value to search radius to avoid rounding issues
Returns:
List[List[int]] containing neighbour indices of every cell.
- hypertiling.neighbors.find_radius_optimized_single(tiling, index, radius=None, eps=1e-05) List[int]
Get adjacent polygons for a single polygon through radius search Compared to its brute-force equivalent, this improved implemention makes sure everything is fully vectorized and complied by numpy, such that we gain a dramatic speed-up
Time complexity: O(n) where n=len(tiling)
Arguments:
- tilingsub-class of Tiling
The hyperbolic tiling object (represented by one of the “kernels”)
- indexint
Index of the cell for which the neighbours are to be found
- radiusfloat
The search radius
- epsfloat
Add small value to search radius to avoid rounding issues
Returns:
[List[int]] containing neighbour indices of every cell.