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 × 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 × 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 triangulation Dx(L) of a finite sampling L of X is homotopy equivalent to X. Moreover, Dx(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) and C ^W _X,v(L). We also present some simulation results in the context of sensor networks that corroborate our theoretical statements.