Geodesic Delaunay triangulation and witness complex in the plane

We introduce a novel feature size for bounded planar domains endowed with an intrinsic metric. Given a point x in such a domain X , the homotopy feature size of X at x , or hfs( x ) for short, measures half the length of the shortest loop through x that is not null-homotopic in X . The resort to an intrinsic metric makes hfs( x ) rather insensitive to the local geometry of X , in contrast with its predecessors (local feature size, weak feature size, homology feature size). This leads to a reduced number of samples that still capture the topology of X. Under reasonable sampling conditions involving hfs, we show that the geodesic Delaunay traingulation D X ( L ) of a finite sampling L of X is homotopy equivalent to X. Moreover, D X ( L ) is sandwiched between the geodesic witness complex C W X ( L ) and a relaxed version C W X, v ( L ), defined by a parameter v. Taking advantage of this fact, we prove that the homology of D X ( L ) (and hence of X ) can be retrieved by computing the persistent homology between C W X ( L ) and C W X, v ( L ). We propose algorithms for estimating hfs, selecting a landmark set of sufficient density, building its geodesic Delaunay triangulation, and computing the homology of X using C W X ( L ). We also present some simulation results in the context of sensor networks that corroborate our theoretical statements.