Testing contractibility in planar rips complexes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Testing contractibility in planar rips complexes

Full text

Pdf (1.03 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-fourth annual symposium on Computational geometry table of contents

College Park, MD, USA

SESSION: 7 table of contents

Pages 251-259

Year of Publication: 2008

ISBN:978-1-60558-071-5

Authors

Erin W. Chambers	UIUC, Urbana, IL, USA
Jeff Erickson	UIUC, Urbana, IL, USA
Pratik Worah	UIUC, Urbana, IL, USA

Sponsors

ACM: Association for Computing Machinery
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 38, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1377676.1377721 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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]