Geometry helps to compare persistence diagrams. (English) Zbl 1414.68129


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
55N35 Other homology theories in algebraic topology
68R10 Graph theory (including graph drawing) in computer science


Zbl 0980.68101
Full Text: DOI arXiv


[1] Aaron Adcock, Daniel Rubin, and Gunnar Carlsson. 2014. Classification of hepatic lesions using the matching metric. Computer Vision and Image Understanding 121 (2014), 36-42.
[2] Pankaj K. Agarwal and Jeff M. Phillips. 2006. On bipartite matching under the RMS distance. In Proceedings of the 18th Annual Canadian Conference on Computational Geometry (CCCG’06).
[3] Pankaj K. Agarwal and R. Sharathkumar. 2014. Approximation algorithms for bipartite matching with metric and geometric costs. In Proceedings of the Symposium on Theory of Computing (STOC’14). 555-564. · Zbl 1315.05104
[4] Alexander Andrievsky and Andrei Sobolevskii. 2008. WANN: An Implementation of Weighted Nearest Neighbor Search. Retrieved from http://www.mccme.ru/ ansobol/otarie/software.html.
[5] Jon L. Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18 (1975), 509-517. · Zbl 0306.68061
[6] Dimitri Bertsekas. 1979. A Distributed Algorithm for the Assignment Problem. Technical Report. Laboratory for Information and Decision Sciences, MIT.
[7] Dimitri Bertsekas. 1988. The auction algorithm: A distributed relaxation method for the assignment problem. Ann. Operat. Res. 14, 1 (1988), 105-123. · Zbl 0788.90055
[8] Dimitri Bertsekas and David Castañon. 1989. The auction algorithm for the transportation problem. Ann. Operat. Res. 20, 1 (1989), 67-96. · Zbl 0705.90061
[9] Dimitri Bertsekas and David Castañon. 1991. Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput. 17, 6 (1991), 707-732. · Zbl 0737.68036
[10] Rainer E. Burkard, Mauro Dell’Amico, and Silvano Martello. 2009. Assignment Problems, Revised Reprint. Society for Industrial and Applied Mathematics, Philadelphia, PA, p. 19104. · Zbl 1196.90002
[11] L. Paul Chew and Klara Kedem. 1992. Improvements on geometric pattern matching problems. In Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory (SWAT’92). 318-325.
[12] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. 2007. Stability of persistence diagrams. Discr. Comput. Geom. 37, 1 (2007), 103-120. · Zbl 1117.54027
[13] David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Yuriy Mileyko. 2010. Lipschitz functions have Lp-stable persistence. Found. Comput. Math. 10, 2 (2010), 127-139. · Zbl 1192.55007
[14] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. 2000. Computational Geometry: Algorithms and Applications (2nd ed.). Springer. · Zbl 0939.68134
[15] Herbert Edelsbrunner and John Harer. 2010. Computational Topology. An Introduction. American Mathematics Society. · Zbl 1193.55001
[16] Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. 2000. Topological persistence and simplification. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS’00). 454-463. · Zbl 1011.68152
[17] Jack Edmonds. 1965. Paths, trees, and flowers. Can. J. Math. 17, 3 (1965), 449-467. · Zbl 0132.20903
[18] Alon Efrat, Alon Itai, and Matthew J. Katz. 2001. Geometry helps in bottleneck matching and related problems. Algorithmica 31, 1 (2001), 1-28. · Zbl 0980.68101
[19] Jennifer Gamble and Giseon Heo. 2010. Exploring uses of persistent homology for statistical analysis of landmark-based shape data. J. Multivar. Anal. 101, 9 (2010), 2184-2199. · Zbl 1203.62116
[20] Chen Gu, Leonidas J. Guibas, and Michael Kerber. 2014. Topology-driven trajectory synthesis with an example on retinal cell motions. In Proceedings of the International Workshop on Algorithms in Bioinformatics (WABI’14). 326-339.
[21] John E. Hopcroft and Richard M. Karp. 1973. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 4 (1973), 225-231. · Zbl 0266.05114
[22] Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov. 2016. Geometry helps to compare persistence diagrams. In Proceedings of the 18th Workshop on Algorithm Engineering and Experiments (ALENEX’16). 103-112. · Zbl 1430.68376
[23] Dmitriy Morozov. 2010. Dionysus Library for Computing Persistent Homology. Retrieved from mrzv.org/software/dionysus.
[24] David M. Mount and Sunil Arya. 2010. ANN: A Library for Approximate Nearest Neighbor Searching. Retrieved from http://www.cs.umd.edu/∼mount/ANN. · Zbl 1204.68103
[25] James Munkres. 1957. Algorithms for the assignment and transportation problems. J. Soc. Industr. Appl. Math. 5, 1 (March 1957), 32-38. · Zbl 0083.15302
[26] R. Sharathkumar and Pankaj K Agarwal. 2012. Algorithms for the transportation problem in geometric settings. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 306-317. · Zbl 1423.90023
[27] Pravin M. Vaidya. 1989. Geometry helps in matching. SIAM J. Comput. 18, 6 (1989), 1201-1225. · Zbl 0692.68042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.