SheehyRipsSimplexStream

The linear-size approximate/sparse Vietoris-Rips filtration of Cavanna, Jahanseir & Sheehy, "A Geometric Perspective on Sparse Filtrations" (arXiv:1506.03797, CCCG 2015) -- checked directly against the paper's own Definitions/Algorithm 1-4 and Lemma 1/Corollary 2/Theorem 5 (.claude/WORKLOG-sheehy-rips.md has the fetched PDF pages and the derivation). This is the GREEDY-PERMUTATION reformulation of Sheehy's original net-tree-based construction (D.R. Sheehy, "Linear-Size Approximations to the Vietoris-Rips Filtration," Discrete & Computational Geometry 49(4), 2013, arXiv:1203.6786) -- simpler to implement correctly and to verify, at the cost of the two papers' own epsilon parameters NOT being directly comparable (Sheehy 2013's approximation factor is 1/(1-2*epsilon); this class's, following CJS 2015, is (1+epsilon)).

'''What this buys you''': a filtration whose persistence barcode is a genuine (1+epsilon)-multiplicative approximation (Theorem 5) to the plain Vietoris-Rips barcode, built from a complex whose SIZE is linear in n (CJS 2015 Lemma 6/7/Theorem 9/10) for point sets of bounded doubling dimension -- dramatically fewer simplices to reduce than plain VR at the same scale range, in exchange for a controlled, quantified loss of precision.

'''What this class does NOT do''': the paper's own O(n log n) algorithm (Section 5, Algorithms 1-4) builds the edges of the sparse filtration directly from the greedy permutation's neighbor structure, touching only kappa^O(d) candidates per point. This class instead computes every pairwise edgeBirth directly (O(n^2), like plain VietorisRips/RipserCofaceSimplexStream's own default candidate enumeration) and lets RipserCofaceSimplexStream's ordinary combinatorial coface generation do the rest. The payoff here is a SMALLER complex to reduce, not a faster one to build -- see the class doc's own honest framing on this point in every other "not the fastest construction" case in this codebase (Cech, Witness, alpha).

==The construction==

Given a greedy permutation (streams.GreedyPermutation, computed by LandmarkSelector.maxmin run to numLandmarks = ambientMetricSpace.size) with insertion radii lambda_p (lambda of the very first point is Double.PositiveInfinity by convention -- it must never be pruned away, since it anchors the whole construction), and a sparsity parameter epsilon in (0,1):

• each point p's ball radius at scale alpha is r_p(alpha) := min(alpha, lambda_p*(1+epsilon)/epsilon) (CJS 2015 Section 3) -- grows with alpha until it saturates;
• p's ball becomes and stays EMPTY once alpha > lambda_p*(1+epsilon)^2/epsilon (vanish(p) below) -- no new simplex may use p past that scale, though the filtration itself never removes anything already present (S^alpha := union_{delta = 1) is born at max over its own edges' birth times, PROVIDED that value is <= min_{p in sigma} vanish(p) -- otherwise it never appears at all (CJS 2015 Section 5.3, "SimplexBirthTime" -- the max/min intersection is valid because balls are convex and pairwise-intersecting convex sets have a common intersection, the same Helly-type fact that makes plain Rips itself a flag/nerve complex).

'''A real gap in CJS 2015's own Algorithm 3, verified, not just suspected''': that algorithm computes an edge's birth from only the TWO endpoints' own thresholds, with no check against vanish -- but Section 5.3's own SimplexBirthTime definition (the general k-simplex rule above) requires exactly that check, and an edge is simply its k=1 case, not a special one. Two independent counterexamples confirm this is a real gap in the published algorithm, not an artifact of skipping its neighbor-search prefilter: epsilon=1, lambda_p=1, lambda_q=10, d=10 (raw formula gives 8, but p vanishes at 4); and, checked directly against the paper's OWN Lemma 6/7 neighbor bound (kappa = (epsilon^2+3*epsilon+2)/epsilon, d(p_i,p_j) <= kappa*2^ceil(lg lambda_i) puts p_j in p_i's own candidate neighbor list), epsilon=1, lambda_p=1.1, lambda_q=10, d=10 -- this pair passes the paper's own restricted neighbor search AND its Algorithm 3 (returning 7.8), while p vanishes at 4.4. Whether the paper's full O(n log n) pipeline compensates for this some other way was not checked; only the gap itself was verified. edgeBirth here applies the vanish clamp Section 5.3 describes to every edge, not just higher simplices.

'''Units''': every OTHER stream in this codebase records filtration values in "diameter" units (an edge's own value is the raw ambient distance, not half of it) -- but CJS 2015's own alpha is a RADIUS parameter (R_alpha := {J : max d(p,q) <= 2*alpha}; their own Algorithm 3 literally returns d/2 in its first branch). Every output this class reports -- edgeBirth's return value and vanish -- is therefore the paper's own value DOUBLED, never lambda itself (an ordinary ambient distance already in diameter-comparable units, entering the formulas unchanged). After doubling, the first (unsparsified) branch collapses to exactly d, matching plain VR's own edge value -- a useful internal sanity check, exercised directly by SheehyRipsStreamSpec's "reduces to plain VR" fixture.

'''maxFiltrationValue''' is always clamped to maxFiniteFiltrationValue -- the largest FINITE simplex birth this construction can ever produce (an honest, data-dependent bound: any finite simplex's value is a max over its own edges, so the largest finite EDGE birth bounds every finite simplex) -- REGARDLESS of what the caller passes (None resolves to exactly that bound; an explicit Some(x) is min(x, maxFiniteFiltrationValue)). This is deliberately NOT metricSpace.minimumEnclosingRadius (this is not a cone construction -- an edge to the anchor point can be unboundedly large, so no point has a finite max distance to every other point), and the clamp is unconditional rather than only a None-default specifically so that an explicit Some(Double.PositiveInfinity) -- how every other stream in this codebase spells "untruncated" -- stays safe here too: keptByThresholdAndCriterion's own <= comparison is plain IEEE-754 Double comparison, under which Double.PositiveInfinity <= Double.PositiveInfinity is true, so an UNCLAMPED literal infinite threshold would silently readmit every simplex this construction is supposed to exclude forever.

'''Not a diameter-only construction''': unlike plain VR (and like the general, non-flag WitnessCofaceSimplexStream and DtmRipsSimplexStream), a simplex's value here is not simply the maximum ambient pairwise distance among its vertices, so matlab.TDA4j refuses engine=ripser for this complex (both Ripser engines' incremental insertionDiameter/apparent-pairs machinery assume the filtration functional literally IS MaximumDistanceFiltrationValue on the metric space handed to them). naive/chunks/cohomology all consume it like any other CofaceSimplexStream[Int, Double]; chunks is cross-validated fresh against naive (SheehyRipsStreamSpec), not assumed to carry over.