Find Exact Sample Fermat Nearest Neighbors

Find nearest neighbors in the complete-graph sample Fermat distance using Euclidean neighbor pruning and truncated Dijkstra searches.

Usage

fermat.knn(points, k, p = 2, rooted = FALSE, algorithm = "kd_tree")

create.fermat.sknn.graph(
  points,
  k,
  p = 2,
  rooted = FALSE,
  algorithm = "kd_tree"
)

Arguments

points: Finite numeric matrix or data frame, observations in rows.
k: Number of other observations to return per row; 1 <= k < n.
p: Finite edge-length exponent at least one.
rooted: Logical; return the 1/p power of path costs if TRUE.
algorithm: Exact Euclidean search algorithm passed to FNN::get.knnx(): "kd_tree" (default) or "brute".

Value

fermat.knn() returns a list with n-by-k matrices index (1-based neighbor indices) and distance (in nondecreasing order), excluding self. create.fermat.sknn.graph() returns a dgraph formed by the union of these directed selections. Its lengths are Fermat distances, not powered direct Euclidean edges. Vertex degrees can exceed k; components are not repaired. Use graph.geodesic.distances() to sum stored lengths, rather than applying fermat.distances() with p > 1 and powering them again.

Details

The unrooted distance is the minimum sum of Euclidean edge lengths raised to p, allowing paths through all observations. Rooting preserves neighbor rankings. Lemma 5.6 of McKenzie and Damelin justifies pruning to directed Euclidean neighbor lists for nearest-neighbor queries. This does not establish equality of all pairwise distances on the sparse graph. The paper counts the source among its neighbors; here k excludes it.

Equal-distance neighbors at the cutoff may be selected arbitrarily; their identities need not agree across search algorithms or permutations. Duplicate observations are retained as distinct vertices with zero distance. Exactness refers to the complete-graph target, subject to floating-point arithmetic. Extremely disparate coordinate scales should be rescaled. Nonfinite computed lengths and powered costs, and positive costs that underflow to zero, cause errors.

Candidate lists and output use O(nk) storage. After Euclidean search, binary-heap path searches take O(nk^2*log(k+1)) time with O(n+k^2) scratch. Euclidean search may be quadratic in n in high dimensions. Unlike the implicit distance backend, this function does not scan every complete-graph edge for numeric-range validation.

References

McKenzie, D. and Damelin, S. (2019). Power Weighted Shortest Paths for Clustering Euclidean Data. Section 5, Lemma 5.6 and Algorithm 2. https://arxiv.org/abs/1905.13345.

Examples

X <- cbind(c(0, 1, 2, 4), 0)
fermat.knn(X, k = 2, p = 2)
#> $index
#>      [,1] [,2]
#> [1,]    2    3
#> [2,]    1    3
#> [3,]    2    1
#> [4,]    3    2
#> 
#> $distance
#>      [,1] [,2]
#> [1,]    1    2
#> [2,]    1    1
#> [3,]    1    2
#> [4,]    4    5
#> 
graph <- create.fermat.sknn.graph(X, k = 2)
graph.edges(graph)
#>   from to length
#> 1    1  2      1
#> 2    1  3      2
#> 3    2  3      1
#> 4    2  4      5
#> 5    3  4      4