thumb|upright=1.2|The offset filtration at six scale parameters on a point cloud sampled from two circles of different sizes. The '''offset filtration''' (also called the '''"union-of-balls"'''<ref>{{Cite journal |last1=Adams |first1=Henry |last2=Moy |first2=Michael |date=2021 |title=Topology Applied to Machine Learning: From Global to Local |journal=Frontiers in Artificial Intelligence |volume=4 |pages=2 |article-number=668302 |doi=10.3389/frai.2021.668302 |issn=2624-8212 |pmc=8160457 |pmid=34056580|doi-access=free }}</ref> or '''"union-of-disks"'''<ref>{{Cite book |last=Edelsbrunner |first=Herbert |title=A short course in computational geometry and topology |date=2014 |isbn=978-3-319-05957-0 |location=Cham |pages=35 |oclc=879343648}}</ref> '''filtration''') is a growing sequence of metric balls used to detect the size and scale of topological features of a data set. The offset filtration commonly arises in persistent homology and the field of topological data analysis. Utilizing a union of balls to approximate the shape of geometric objects was first suggested by Frosini in 1992 in the context of submanifolds of Euclidean space.<ref>{{Cite book |last=Frosini |first=Patrizio |date=1992-02-01 |editor-last=Casasent |editor-first=David P. |title=Intelligent Robots and Computer Vision X: Algorithms and Techniques |chapter=Measuring shapes by size functions |series=Proceedings of SPIE |volume=1607 |chapter-url=http://proceedings.spiedigitallibrary.org/proceeding.aspx?articleid=980889 |location=Boston, MA |pages=122–133 |doi=10.1117/12.57059|bibcode=1992SPIE.1607..122F |s2cid=121295508 |chapter-url-access=subscription }}</ref> The construction was independently explored by Robins in 1998, and expanded to considering the collection of offsets indexed over a series of increasing scale parameters (i.e., a growing sequence of balls), in order to observe the stability of topological features with respect to attractors.<ref>{{Cite journal |last=Robins |first=Vanessa |date=1999-01-01 |title=Towards computing homology from approximations |url=http://topology.nipissingu.ca/tp/reprints/v24/tp24222.pdf |journal=Topology Proceedings |volume=24 |pages=503–532}}</ref> Homological persistence as introduced in these papers by Frosini and Robins was subsequently formalized by Edelsbrunner et al. in their seminal 2002 paper ''Topological Persistence and Simplification.''<ref>{{Cite journal |last1=Edelsbrunner |last2=Letscher |last3=Zomorodian |date=2002 |title=Topological Persistence and Simplification |journal=Discrete & Computational Geometry |language=en |volume=28 |issue=4 |pages=511–533 |doi=10.1007/s00454-002-2885-2 |issn=0179-5376|doi-access=free }}</ref> Since then, the offset filtration has become a primary example in the study of computational topology and data analysis.
== Definition == Let <math>X</math> be a finite set in a metric space <math>(M,d)</math>, and for any <math>x\in X</math> let <math>B(x,\varepsilon) = \{y\in X \mid d(x,y) \leq \varepsilon \}</math> be the closed ball of radius <math>\varepsilon</math> centered at <math>x</math>. Then the union <math display="inline">X^{(\varepsilon)}:=\bigcup_{x\in X} B(x,\varepsilon)</math> is known as the offset of <math>X</math> with respect to the parameter <math>\varepsilon</math> (or simply the <math>\varepsilon</math>-offset of <math>X</math>).
By considering the collection of offsets over all <math>\varepsilon \in [0,\infty)</math> we get a family of spaces <math>\mathcal O(X) := \{ X^{(\varepsilon)} \mid \varepsilon \in [0,\infty)\}</math> where <math>X^{(\varepsilon)}\subseteq X^{(\varepsilon^\prime)}</math> whenever <math>\varepsilon \leq \varepsilon^\prime</math>. So <math>\mathcal O(X)</math> is a family of nested topological spaces indexed over <math>\varepsilon</math>, which defines a filtration known as the '''offset filtration''' on <math>X</math>.<ref>{{Citation |last1=Halperin |first1=Dan |title=The Offset Filtration of Convex Objects |date=2015 |url=http://link.springer.com/10.1007/978-3-662-48350-3_59 |work=Algorithms - ESA 2015 |volume=9294 |pages=705–716 |editor-last=Bansal |editor-first=Nikhil |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-662-48350-3_59 |isbn=978-3-662-48349-7 |access-date=2023-02-25 |last2=Kerber |first2=Michael |last3=Shaharabani |first3=Doron |series=Lecture Notes in Computer Science |arxiv=1407.6132 |s2cid=660889 |editor2-last=Finocchi |editor2-first=Irene}}</ref>
Note that it is also possible to view the offset filtration as a functor <math>\mathcal O(X) : [0, \infty) \to \mathbf{Top}</math> from the poset category of non-negative real numbers to the category of topological spaces and continuous maps.<ref>{{Cite journal |last1=Bauer |first1=Ulrich |last2=Kerber |first2=Michael |last3=Roll |first3=Fabian |last4=Rolle |first4=Alexander |date=2023-02-16 |title=A unified view on the functorial nerve theorem and its variations |journal=Expositiones Mathematicae |volume=41 |issue=4 |pages=8 |doi=10.1016/j.exmath.2023.04.005 |arxiv=2203.03571|s2cid=247291819 }}</ref><ref>{{Cite journal |last1=Blumberg |first1=Andrew J. |last2=Lesnick |first2=Michael |date=2022-10-17 |title=Stability of 2-Parameter Persistent Homology |url=https://link.springer.com/10.1007/s10208-022-09576-6 |journal=Foundations of Computational Mathematics |volume=24 |issue=2 |pages=385–427 |language=en |doi=10.1007/s10208-022-09576-6 |arxiv=2010.09628 |s2cid=224705357 |issn=1615-3375}}</ref> There are some advantages to the categorical viewpoint, as explored by Bubenik and others.<ref name=":0">{{Cite journal |last1=Bubenik |first1=Peter |last2=Scott |first2=Jonathan A. |date=2014 |title=Categorification of Persistent Homology |url=http://link.springer.com/10.1007/s00454-014-9573-x |journal=Discrete & Computational Geometry |language=en |volume=51 |issue=3 |pages=600–627 |doi=10.1007/s00454-014-9573-x |s2cid=254027425 |issn=0179-5376|arxiv=1205.3669 }}</ref>
== Properties == A standard application of the nerve theorem shows that the union of balls has the same homotopy type as its nerve, since closed balls are convex and the intersection of convex sets is convex.<ref>{{Cite book |last=Edelsbrunner |first=Herbert |title=Proceedings of the ninth annual symposium on Computational geometry - SCG '93 |chapter=The union of balls and its dual shape |date=1993 |chapter-url=http://portal.acm.org/citation.cfm?doid=160985.161139 |language=en |location=San Diego, California, United States |publisher=ACM Press |pages=218–231 |doi=10.1145/160985.161139 |isbn=978-0-89791-582-3|s2cid=9599628 }}</ref> The nerve of the union of balls is also known as the Čech complex,<ref>{{Cite arXiv |last1=Kim |first1=Jisu |last2=Shin |first2=Jaehyeok |last3=Chazal |first3=Frédéric |last4=Rinaldo |first4=Alessandro |last5=Wasserman |first5=Larry |date=2020-05-12 |title=Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex |class=math.AT |eprint=1903.06955}}</ref> which is a subcomplex of the Vietoris-Rips complex.<ref>{{Cite book |last=Edelsbrunner |first=Herbert |title=Computational topology : an introduction |date=2010 |publisher=American Mathematical Society |others=J. Harer |isbn=978-0-8218-4925-5 |location=Providence, R.I. |pages=61 |oclc=427757156}}</ref> Therefore the offset filtration is weakly equivalent to the Čech filtration (defined as the nerve of each offset across all scale parameters), so their homology groups are isomorphic.<ref>{{Cite journal |last1=Chazal |first1=Frédéric |last2=Michel |first2=Bertrand |date=2021 |title=An Introduction to Topological Data Analysis: Fundamental and Practical Aspects for Data Scientists |journal=Frontiers in Artificial Intelligence |volume=4 |article-number=667963 |doi=10.3389/frai.2021.667963 |issn=2624-8212 |pmc=8511823 |pmid=34661095|doi-access=free }}</ref>
Although the Vietoris-Rips filtration is not identical to the Čech filtration in general, it is an approximation in a sense. In particular, for a set <math>X \subset \mathbb R^d</math> we have a chain of inclusions <math>\operatorname{Rips}_\varepsilon(X) \subset \operatorname{Cech}_{\varepsilon^\prime}(X) \subset \operatorname{Rips}_{\varepsilon^\prime}(X)</math> between the Rips and Čech complexes on <math>X</math> whenever <math>\varepsilon^\prime / \varepsilon \geq \sqrt{2d/d+1}</math>.<ref>{{Cite journal |last1=de Silva |first1=Vin |last2=Ghrist |first2=Robert |date=2007-04-25 |title=Coverage in sensor networks via persistent homology |url=http://www.msp.org/agt/2007/7-1/p16.xhtml |journal=Algebraic & Geometric Topology |language=en |volume=7 |issue=1 |pages=339–358 |doi=10.2140/agt.2007.7.339 |issn=1472-2739|doi-access=free }}</ref> In general metric spaces, we have that <math>\operatorname{Cech}_\varepsilon(X) \subset \operatorname{Rips}_{2\varepsilon}(X) \subset \operatorname{Cech}_{2\varepsilon}(X)</math> for all <math>\varepsilon >0</math>, implying that the Rips and Cech filtrations are 2-interleaved with respect to the interleaving distance as introduced by Chazal et al. in 2009.<ref>{{Cite book |last1=Anai |first1=Hirokazu |last2=Chazal |first2=Frédéric |last3=Glisse |first3=Marc |last4=Ike |first4=Yuichi |last5=Inakoshi |first5=Hiroya |last6=Tinarrage |first6=Raphaël |last7=Umeda |first7=Yuhei |title=Topological Data Analysis |date=2020-05-26 |chapter= |series=Abel Symposia |volume=15 |doi=10.1007/978-3-030-43408-3 |arxiv=1811.04757|isbn=978-3-030-43407-6 |s2cid=242491854 }}</ref><ref name=":1">{{Cite book |last1=Chazal |first1=Frédéric |last2=Cohen-Steiner |first2=David |last3=Glisse |first3=Marc |last4=Guibas |first4=Leonidas J. |last5=Oudot |first5=Steve Y. |title=Proceedings of the twenty-fifth annual symposium on Computational geometry |chapter=Proximity of persistence modules and their diagrams |date=2009-06-08 |chapter-url=https://dl.acm.org/doi/10.1145/1542362.1542407 |language=en |location=Aarhus Denmark |publisher=ACM |pages=237–246 |doi=10.1145/1542362.1542407 |isbn=978-1-60558-501-7|s2cid=840484 |url=https://hal.inria.fr/hal-02292996/file/stable.pdf }}</ref>
It is a well-known result of Niyogi, Smale, and Weinberger that given a sufficiently dense random point cloud sample of a smooth submanifold in Euclidean space, the union of balls of a certain radius recovers the homology of the object via a deformation retraction of the Čech complex.<ref>{{Cite journal |last1=Niyogi |first1=Partha |last2=Smale |first2=Stephen |last3=Weinberger |first3=Shmuel |date=2008 |title=Finding the Homology of Submanifolds with High Confidence from Random Samples |journal=Discrete & Computational Geometry |language=en |volume=39 |issue=1–3 |pages=419–441 |doi=10.1007/s00454-008-9053-2 |s2cid=1788129 |issn=0179-5376|doi-access=free }}</ref>
The offset filtration is also known to be stable with respect to perturbations of the underlying data set. This follows from the fact that the offset filtration can be viewed as a sublevel-set filtration with respect to the distance function of the metric space. The stability of sublevel-set filtrations can be stated as follows: Given any two real-valued functions <math>\gamma, \kappa</math> on a topological space <math>T</math> such that for all <math>i\geq 0</math>, the <math>i\text{th}</math>-dimensional homology modules on the sublevel-set filtrations with respect to <math>\gamma, \kappa</math> are point-wise finite dimensional, we have <math>d_B (\mathcal B_i (\gamma), \mathcal B_i (\kappa)) \leq d_\infty (\gamma, \kappa)</math> where <math>d_B(-)</math> and <math>d_\infty(-)</math> denote the bottleneck and sup-norm distances, respectively, and <math>\mathcal B_i (-)</math> denotes the <math>i\text{th}</math>-dimensional persistent homology barcode.<ref>{{Cite journal |last1=Cohen-Steiner |first1=David |last2=Edelsbrunner |first2=Herbert |last3=Harer |first3=John |date=2007 |title=Stability of Persistence Diagrams |journal=Discrete & Computational Geometry |language=en |volume=37 |issue=1 |pages=103–120 |doi=10.1007/s00454-006-1276-5 |issn=0179-5376|doi-access=free }}</ref> While first stated in 2005, this sublevel stability result also follows directly from an algebraic stability property sometimes known as the "Isometry Theorem,"<ref name=":0" /> which was proved in one direction in 2009,<ref name=":1" /> and the other direction in 2011.<ref>{{Cite journal |last=Lesnick |first=Michael |date=2015 |title=The Theory of the Interleaving Distance on Multidimensional Persistence Modules |url=http://link.springer.com/10.1007/s10208-015-9255-y |journal=Foundations of Computational Mathematics |language=en |volume=15 |issue=3 |pages=613–650 |doi=10.1007/s10208-015-9255-y |arxiv=1106.5305 |s2cid=254158297 |issn=1615-3375}}</ref><ref>{{Cite journal |last=Lesnick |first=Michael |date=2023 |title=Lecture notes for AMAT 840: Multiparameter Persistence |url=https://www.albany.edu/~ML644186/840_2022/Math840_Notes_22.pdf |journal=University at Albany, SUNY}}</ref>
A multiparameter extension of the offset filtration defined by considering points covered by multiple balls is given by the multicover bifiltration, and has also been an object of interest in persistent homology and computational geometry.<ref>{{Cite journal |last1=Corbet |first1=René |last2=Kerber |first2=Michael |last3=Lesnick |first3=Michael |last4=Osang |first4=Georg |date=2023-02-20 |title=Computing the Multicover Bifiltration |journal=Discrete & Computational Geometry |volume=70 |issue=2 |pages=376–405 |language=en |doi=10.1007/s00454-022-00476-8 |pmid=37581017 |pmc=10423148 |issn=0179-5376|arxiv=2103.07823 }}</ref><ref>{{Cite journal |last1=Edelsbrunner |first1=Herbert |last2=Osang |first2=Georg |date=2021 |title=The Multi-Cover Persistence of Euclidean Balls |journal=Discrete & Computational Geometry |language=en |volume=65 |issue=4 |pages=1296–1313 |doi=10.1007/s00454-021-00281-9 |issn=0179-5376 |pmc=8550220 |pmid=34720303}}</ref>
==References== {{Reflist}} Category:Applied mathematics Category:Computational topology Category:Geometric topology Category:Data analysis