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 DX (L) of a finite sampling L of X is homotopy equivalent to X. Moreover, DX (L) is sandwiched between the geodesic witness complex CWX (L) and a relaxed version CWX, v (L), defined by a parameter v. Taking advantage of this fact, we prove that the homology of DX (L) (and hence of X) can be retrieved by computing the persistent homology between CWX (L) and CWX, 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 CWX (L). We also present some simulation results in the context of sensor networks that corroborate our theoretical statements.