Morse Theory for the k-NN Distance Function

2024/03/19 by Yohai Reani, Reani, Yohai, Omer Bobrowski +1 · 1 citation
Computer Science · #Algebraic Topology (math.AT) #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.2403.12792

openalex publication_date 2024/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the k-th nearest neighbor distance function from a finite point-set in ℝ^d. We provide a Morse theoretic framework to analyze the sub-level set topology. In particular, we present a simple combinatorial-geometric characterization for critical points and their indices, along with detailed information about the possible changes in homology at the critical levels. We conclude by computing the expected number of critical points for a homogeneous Poisson process. Our results deliver significant insights and tools for the analysis of persistent homology in order-k Delaunay mosaics, and random k-fold coverage.

Cited by

• Sharp Phase Transitions for k-Fold Coverage Using Morse Theory

Related

• The distance function to a finite set is a topological Morse function
• Morse theory of Euclidean distance functions from algebraic hypersurfaces
• Power diagrams and Morse Theory
• Distance Functions, Critical Points, and the Topology of Random Čech Complexes
• Generalized Morse Theory of Distance Functions to Surfaces for Persistent Homology