Testing contractibility in planar rips complexes

ABSTRACT

The (Vietoris-)Rips complex of a discrete point-set P is an abstract simplicial complex in which a subset of P defines a simplex if and only if the diameter of that subset is at most 1. We describe an efficient algorithm to determine whether a given cycle in a planar Rips complex is contractible. Our algorithm requires O(m log n) time to preprocess a set of n points in the plane in which m pairs have distance at most 1; after preprocessing, deciding whether a cycle of k Rips edges is contractible requires O(k) time. We also describe an algorithm to compute the shortest non-contractible cycle in a planar Rips complex in O(n²log n + mn) time.

REFERENCES

• 1: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 2: Sergei Bespamyatnikh, Computing homotopic shortest paths in the plane, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: S. Bespamyatnikh. Encoding homotopy of paths in the plane. phProc. LATIN 2004: Theoretical Infomatics, 329--338, 2004. Lect. Notes Comput. Sci. 2976, Springer-Verlag.
• 4: Sergio Cabello, Many distances in planar graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1213-1220, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109691]
• 5: S. Cabello, Y. Liu, A. Mantler, and J. Snoeyink. Testing homotopy for paths in the plane. Discrete Comput. Geom. 31(1):61--81, 2004.
• 6: Sergio Cabello , Bojan Mohar, Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs, Discrete & Computational Geometry, v.37 n.2, p.213-235, February 2007 [doi>10.1007/s00454-006-1292-5]
• 7: E. Carlsson, G. Carlsson, and V. de Silva. An algebraic topological method for feature identification. Intl. J. Comput. Geom. Appl. 16(4):291--314, 2006.
• 8: G. Carlsson. Persistent homology and the analysis of high dimensional data. Presentation at the Symposium on the Geometry of Very Large Data Sets, Fields Institute for Research in Mathematical Sciences, February 24, 2005. http://comptop.stanford.edu/preprints/ottawa.pdf.
• 9: G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian. On the local behaevior of spaces of natural images. Preprint, 2006.
• 10: G. Carlsson, A. Zomorodian, A. Collins, and L. J. Guibas. Persistence barcodes for shapes. Int. J. Shape Modeling 11(2):149--187, 2005.
• 11: Sergio Cabello , Erin W. Chambers, Multiple source shortest paths in a genus g graph, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.89-97, January 07-09, 2007, New Orleans, Louisiana
• 12: Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137918]
• 13: E. W. Chambers, V. de Silva, J. Erickson, and R. Ghrist. Rips complexes of planar point sets. Preprint, 2007, ArXiv:0712.0395.
• 14: Bernard Chazelle , Micha Sharir , Emo Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Proceedings of the sixth annual symposium on Computational geometry, p.23-33, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98532]
• 15: Éric Colin de Verdière , Jeff Erickson, Tightening non-simple paths and cycles on surfaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.192-201, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109580]
• 16: É. Colin de Verdière and F. Lazarus. Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33(3):507--534, 2005.
• 17: Erik D. Demaine , MohammadTaghi Hajiaghayi , Bojan Mohar, Approximation algorithms via contraction decomposition, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.278-287, January 07-09, 2007, New Orleans, Louisiana
• 18: Tamal K. Dey , Sumanta Guha, Transforming curves on surfaces, Journal of Computer and System Sciences, v.58 n.2, p.297-325, April 1999 [doi>10.1006/jcss.1998.1619]
• 19: T. K. Dey and H. Schipper. A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Comput. Geom. 14:93--110, 1995.
• 20: C. A. Duncan, A. Efrat, S. G. Kobourov, and C. Wenk. Drawing with fat edges. Int. J. Found. Comput. Sci. 17(5):1143--1164, 2006.
• 21: H. Edelsbrunner. The union of balls and its dual shape. Discrete Comput. Geom. 13:415--440, 1995.
• 22: Herbert Edelsbrunner , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Geometry and Topology for Mesh Generation (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
• 23: H. Edelsbrunner and J. Harer. Persistent homology: A survey. Discrete & Computational Topology: Twenty Years Later, to appear. AMS Press. http://www.cs.duke.edu/ edels/BookSurv/PersistenceSurvey.pdf.
• 24: H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom. 28(4):511--533, 2002.
• 25: Alon Efrat , Stephen G. Kobourov , Anna Lubiw, Computing homotopic shortest paths efficiently, Computational Geometry: Theory and Applications, v.35 n.3, p.162-172, October 2006 [doi>10.1016/j.comgeo.2006.03.003]
• 26: J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1):37--59, 2004.
• 27: Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 28: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 29: R. Ghrist. Barcodes: The persistent topology of data. Preprint, 2007. http://www.math.uiuc.edu/ ghrist/preprints/barcodes.pdf.
• 30: Robert Ghrist , Abubakr Muhammad, Coverage and hole-detection in sensor networks via homology, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 31: D. Grigoriev , A. Slissenko, Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.17-24, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281528]
• 32: M. Gromov. Hyperbolic groups. Essays in Group Theory, 75--265, 1987. MSRI Publications 8, Springer-Verlag.
• 33: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 34: A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http://www.math.cornell.edu/~hatcher/.
• 35: J.-C. Hausmann. On the Vietoris-Rips complexes and a cohomology theory for metric spaces. Prospects in Topology: Proceedings of a Conference in Honor of William Browder, 157--188, 1995. Ann. Math. Stud. 138, Princeton Univ. Press.
• 36: John Hershberger , Jack Snoeyink, Computing minimum length paths of a given homotopy class, Computational Geometry: Theory and Applications, v.4 n.2, p.63-97, June 1994 [doi>10.1016/0925-7721(94)90010-8]
• 37: John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Journal of Algorithms, v.18 n.3, p.403-431, May 1995
• 38: Ken-ichi Kawarabayashi , Buce Reed, Computing crossing number in linear time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250848]
• 39: Martin Kutz, Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137919]
• 40: J. Latschev. Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold. Archiv der Mathematik 77(6):522--528, 2001.
• 41: Francis Lazarus , Michel Pocchiola , Gert Vegter , Anne Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry, p.80-89, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378630]
• 42: A. A. Markov. Insolubility of the problem of homeomorphy. Proceedings of the International Congress of Mathematics, 14--21, 1958. Cambridge University Press.
• 43: J. Matoušek. Spanning trees with low crossing numbers. Informatique Théorique et Applications 6(25):103--123, 1991.
• 44: B. Mohar and C. Thomassen. Graphs on Surfaces. Jons Hopkins Univ. Press, 2001.
• 45: A. Muhammad and A. Jadbabaie. Asymptotic stability of switched higher order Laplacians and dynamic coverage. Hybrid Systems: Computation and Control, p. to appear, 2007. Lecture Notes Comput. Sci., Springer--Verlag. http://www.seas.upenn.edu/~jadbabai/papers/Muhammad_Jadbabaie_HSCC07_FinalSubmission.pdf.
• 46: A. Muhammad and A. Jadbabaie. Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians. Proceedings of Robotics: Science and Systems, p. to appear, 2007. http://www.seas.upenn.edu/ jadbabai/papers/RSS_FINAL.pdf.
• 47: J. Stillwell. Classical Topology and Combinatorial Group Theory, 2nd edition. Graduate Texts in Mathematics 72. Springer-Verlag, 1993.
• 48: C. Thomassen, Embeddings of graphs with no short noncontractible cycles, Journal of Combinatorial Theory Series B, v.48 n.2, p.155-177, Apr. 1990 [doi>10.1016/0095-8956(90)90115-G]
• 49: É. C. de Verdière and F. Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. Proc. 11th Int. Symp. Graph Drawing, 478--490, 2003.
• 50: L. Vietoris. Über den hoheren Zusammenhang kompakter Raume und eine Klasse von zusammenhangstreuen Abbildungen. Math. Ann. 97:454--472, 1927.
• 51: Emo Welzl, On Spanning Trees with Low Crossing Numbers, Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, p.233-249, January 1992
• 52: Zoë Wood , Hugues Hoppe , Mathieu Desbrun , Peter Schröder, Removing excess topology from isosurfaces, ACM Transactions on Graphics (TOG), v.23 n.2, p.190-208, April 2004 [doi>10.1145/990002.990007]
• 53: Afra J. Zomorodian , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Topology for Computing (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2005
• 54: Afra Zomorodian , Gunnar Carlsson, Computing Persistent Homology, Discrete & Computational Geometry, v.33 n.2, p.249-274, February 2005 [doi>10.1007/s00454-004-1146-y]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Performance

Keywords:
computational topology, homotopy, rips shadow, vietoris-rips complex