[1] Mahmuda Ahmed, Brittany Terese Fasy, Matt Gibson, and Carola Wenk. Choosing thresholds for density-based map construction algorithms. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '15, pages 24:1–24:10, New York, NY, USA, 2015. ACM. [ DOI | http ]
[2] Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Graph reconstruction by discrete Morse theory. In 34th International Symposium on Computational Geometry, pages 31:1–31:15, 2018.
[3] Xiaoyin Ge, Issam Safa, Mikhail Belkin, and Yusu Wang. Data skeletonization via reeb graphs. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS'11, pages 837–845, USA, 2011. Curran Associates Inc. [ http ]
[4] Suyi Wang, Yusu Wang, and Yanjie Li. Efficient map reconstruction and augmentation via topological methods. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS '15, pages 1–10. ACM Press, 2015. [ DOI | http ]
[5] Robin Forman. A user's guide to discrete Morse theory. Séminaire Lotharingien de Combinatiore, (48):Art. B48c, 2002.
[6] Sushovan Majhi, Jeffrey Vitter, and Carola Wenk. Approximating Gromov-Hausdorff Distance in Euclidean Space. arXiv:1912.13008 [math.MG], 2019. [ arXiv | http ]
[7] Mikhael Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces.
[8] Helmut Alt, Bernd Behrends, and Johannes Blömer. Approximate matching of polygonal shapes. Annals of Mathematics and Artificial Intelligence, 13(3):251–265, Sep 1995. [ DOI | http ]
[9] Claire Kenyon, Yuval Rabani, and Alistair Sinclair. Low distortion maps between point sets. SIAM J. Comput., 39(4):1617–1636, December 2009. [ DOI | http ]
[10] Facundo Memoli. On the use of Gromov-Hausdorff Distances for Shape Comparison. In M. Botsch, R. Pajarola, B. Chen, and M. Zwicker, editors, Eurographics Symposium on Point-Based Graphics. The Eurographics Association, 2007. [ DOI ]
[11] Günter Rote. Computing the minimum hausdorff distance between two point sets on a line under translation. Information Processing Letters, 38(3):123 – 127, 1991. [ DOI | http ]
Given two sets of points on a line, we want to translate one of them so that their Hausdorff distance (the maximum of the distances from a point in any of the sets to the nearest point in the other set) is as small as possible. We present an optimal O(n log n) algorithm for this problem.

[12] M. Artin. Algebra. Pearson Prentice Hall, 2011. [ http ]
[13] Marcel Berger. Encounter with a Geometer, Part I. 47(2):12, 2000.
[14] Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, and Yusu Wang. Computing the gromov-hausdorff distance for metric trees. ACM Trans. Algorithms, 14(2):24:1–24:20, April 2018. [ DOI | http ]
[15] Dmitri Burago, Yuri Burago, and Sergei Ivanov. A Course in Metric Geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, June 2001. [ DOI | http ]
[16] Facundo Mémoli and Guillermo Sapiro. A Theoretical and Computational Framework for Isometry Invariant Recognition of Point Cloud Data. Foundations of Computational Mathematics, 5(3):313–347, July 2005. [ DOI | http ]
[17] Facundo Mémoli. Gromov-Hausdorff distances in Euclidean spaces. In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pages 1–8, Anchorage, AK, USA, June 2008. IEEE. [ DOI | http ]
[18] Facundo Mémoli. Some Properties of Gromov-Hausdorff Distances. Discrete & Computational Geometry, 48(2):416–440, September 2012. [ DOI | http ]
[19] Alexander Ivanov, Stavros Iliadis, and Alexey Tuzhilin. Realizations of Gromov-Hausdorff Distance. arXiv:1603.08850 [math], March 2016. arXiv: 1603.08850. [ http ]
[20] Mikhael Gromov. Metric structures for Riemannian and non-Riemannian spaces. Modern Birkhäuser classics. Birkhäuser, Boston, 2007.
[21] Elena Farahbakhsh Touli and Yusu Wang. FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees. arXiv:1811.02425 [cs], November 2018. arXiv: 1811.02425. [ http ]
[22] Alexander Hall and Christos Papadimitriou. Approximating the Distortion. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, volume 3624, pages 111–122. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005. [ DOI | http ]
[23] Claire Kenyon, Yuval Rabani, and Alistair Sinclair. Low Distortion Maps Between Point Sets. SIAM Journal on Computing, 39(4):1617–1636, January 2010. [ DOI | http ]
[24] Christos Papadimitriou and Shmuel Safra. The complexity of low-distortion embeddings between point sets. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pages 112–118, USA, 2005. Society for Industrial and Applied Mathematics.
[25] Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel. Efficient Computation of Isometry‐Invariant Distances Between Surfaces. SIAM Journal on Scientific Computing, 28(5):1812–1836, January 2006. [ DOI | http ]
[26] Esther M. Arkin, Klara Kedem, Joseph S. B. Mitchell, Josef Sprinzak, and Michael Werman. Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms. ORSA Journal on Computing, 4(4):375–386, November 1992. [ DOI | http ]
[27] Brittany Terese Fasy, Rafal Komendarczyk, Sushovan Majhi, and Carola Wenk. On the Reconstruction of Geodesic Subspaces of Rn. arXiv:1810.10144 [math.AT], 2018. [ arXiv | http ]
[28] Brittany Terese Fasy, Rafal Komendaczyk, Sushovan Majhi, and Carola Wenk. Topological reconstruction of metric graphs in Rn. In Fall Workshop on Computational Geometry, New York, NY, October 2017. [ http ]
[29] Brittany Terese Fasy, Sushovan Majhi, and Carola Wenk. Threshold-based graph reconstruction using discrete Morse theory. In Fall Workshop on Computational Geometry, New York, NY, November 2018. [ http ]
[30] Henry Adams and Joshua Mirth. Metric thickenings of Euclidean submanifolds. Topology and its Applications, 254:69–84, Mar 2019. [ DOI ]
[31] Michal Adamaszek, Florian Frick, and Adrien Vakili. On homotopy types of Euclidean Rips complexes. Discrete Comput. Geom., 58(3):526–542, October 2017. [ DOI | http ]
[32] Jean-Claude Hausmann. On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces. In Frank Quinn, editor, Prospects in Topology (AM-138), Proceedings of a Conference in Honor of William Browder. (AM-138), pages 175–188. Princeton University Press, 1995.
[33] J. Latschev. Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold. Archiv der Mathematik, 77(6):522–528, December 2001. [ DOI ]
[34] D. N. Kozlov. Combinatorial algebraic topology. Number v. 21 in Algorithms and computation in mathematics. Springer.
[35] Frédéric Chazal, Ruqi Huang, and Jian Sun. Gromov–hausdorff approximation of filamentary structures using reeb-type graphs. Discrete & Computational Geometry, 53(3):621–649, Apr 2015. [ DOI ]
[36] Heinrich Jung. Ueber die kleinste Kugel, die eine räumliche Figur einschliesst. Journal für die reine und angewandte Mathematik, 123:241–257, 1901.
[37] Heinrich W.E. Jung. Über den kleinsten Kreis, der eine ebene Figur einschliesst. Journal für die reine und angewandte Mathematik, 137:310–313, 1910.
[38] M. Gromov, J. Lafontaine, and P. Pansu. Metric Structures for Riemannian and Non-Riemannian Spaces. Progress in Mathematics - Birkhäuser. Birkhäuser, 1999.
[39] Frédéric Chazal, Leonidas J. Guibas, Steve Y. Oudot, and Primoz Skraba. Scalar field analysis over point cloud data. Discrete & Computational Geometry, 46(4):743, May 2011. [ DOI ]
[40] Fabrizio Lecci, Alessandro Rinaldo, and Larry Wasserman. Statistical analysis of metric graph reconstruction. J. Mach. Learn. Res., 15(1):3425–3446, January 2014.
[41] Dominique Attali, André Lieutier, and David Salinas. Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes. Computational Geometry, 46(4):448 – 465, 2013. 27th Annual Symposium on Computational Geometry (SoCG 2011). [ DOI ]
[42] Vin De Silva and Gunnar Carlsson. Topological estimation using witness complexes. In Proceedings of the First Eurographics Conference on Point-Based Graphics, SPBG'04, pages 157–166, Aire-la-Ville, Switzerland, Switzerland, 2004. Eurographics Association. [ DOI ]
[43] Erin W. Chambers, Vin de Silva, Jeff Erickson, and Robert Ghrist. Vietoris–Rips complexes of planar point sets. Discrete & Computational Geometry, 44(1):75–90, Jul 2010. [ DOI ]
[44] Frédéric Cazals and Joachim Giesen. Delaunay Triangulation Based Surface Reconstruction: Ideas and Algorithms. Technical Report RR-5393, INRIA, November 2004. [ .pdf ]
[45] Frédéric Chazal and S. Y. Oudot. Towards persistence-based reconstruction in Euclidean spaces. In Proc. 24th ACM Sympos. Comput. Geom., pages 232–241, 2008.
[46] Frédéric Chazal and Jian Sun. Gromov-Hausdorff approximation of metric spaces with linear structure. CoRR, abs/1305.1172, 2013. [ arXiv ]
[47] D. Burago, I.U.D. Burago, I.U.D. Burago, J.D. Burago, Y. Burago, I.U.D. Burago, S. Ivanov, S. Ivanov, and American Mathematical Society. A Course in Metric Geometry. Crm Proceedings & Lecture Notes. American Mathematical Society, 2001.
[48] Mikhael Gromov. Homotopical effects of dilatation. J. Differential Geom., 13(3):303–310, 1978.
[49] Mikhael Gromov. Filling Riemannian manifolds. J. Differential Geom., 18(1):1–147, 1983.
[50] John M. Sullivan. Curves of Finite Total Curvature, pages 137–161. Birkhäuser Basel, Basel, 2008.
[51] Edwin H Spanier. Algebraic topology, volume 55. Springer Science & Business Media, 1994.
[52] Mahmuda Ahmed, Brittany Terese Fasy, Kyle S. Hickmann, and Carola Wenk. A path-based distance for street map comparison. ACM Trans. Spatial Algorithms Syst., 1(1):3:1–3:28, July 2015. [ DOI ]
[53] Tamal K. Dey. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics). Cambridge University Press, New York, NY, USA, 2006.
[54] Paul Alexandroff. Über den allgemeinen Dimensionsbegriff und seine Beziehungen zur elementaren geometrischen Anschauung. Mathematische Annalen, 98(1):617–635, March 1928. [ DOI ]
[55] Mahmuda Ahmed, Brittany Terese Fasy, and Carola Wenk. Local persistent homology based distance between maps. In Proceedings of the 22Nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '14, pages 43–52, New York, NY, USA, 2014. ACM. [ DOI ]
[56] Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, and Carola Wenk. Map Construction Algorithms. Springer, 2015.
[57] Nina Amenta, Marshall Bern, and David Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical models and image processing, 60(2):125–135, 1998.
[58] Fabrizio Lecci, Alessandro Rinaldo, and Larry A Wasserman. Statistical analysis of metric graph reconstruction. Journal of Machine Learning Research, 15(1):3425–3446, 2014.
[59] Mridul Aanjaneya, Frédéric Chazal, Daniel Chen, Marc Glisse, Leonidas Guibas, and Dmitriy Morozov. Metric graph reconstruction from noisy data. International Journal of Computational Geometry & Applications, 22(04):305–325, 2012.
[60] André Lieutier. Any open bounded subset of Rn has the same homotopy type as its medial axis. Computer-Aided Design, 36(11):1029–1046, 2004.
[61] Nina Amenta and Marshall Bern. Surface reconstruction by voronoi filtering. Discrete & Computational Geometry, 22(4):481–504, 1999.
[62] Frédéric Chazal, David Cohen-Steiner, and André Lieutier. A sampling theory for compact sets in Euclidean space. Discrete & Computational Geometry, 41(3):461–479, 2009.
[63] Frédéric Chazal and André Lieutier. The λ-medial axis. Graphical Models, 67(4):304–331, 2005.
[64] Frédéric Chazal and André Lieutier. Stability and computation of topological invariants of solids in Rn. Discrete & Computational Geometry, 37(4):601–617, 2007.
[65] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103–120, 2007. [ DOI ]
[66] James R. Munkres. Elements Of Algebraic Topology. Addison-Wesley Publishing Company, Second edition, 1996.
[67] James R. Munkres. Topology. Featured Titles for Topology Series. Prentice Hall, Incorporated, 2000.
[68] Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars. Computational Geometry. Springer, Third edition, 2008.
[69] Allen Hatcher. Algebraic Topology. Cambridge University Press, First edition, 2002.
[70] Gunnar Carlsson. Topology and data. Bull. Amer. Math Soc., 46:255–308, 2009. [ DOI ]
[71] David M. Mount. Computational Geometry. Lecture Notes, 2014.
[72] Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete And Computational Geometry, 39. 1-3:419–441, 2008.

This file was generated by bibtex2html 1.98.