Analyzing rigidity with pebble games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Analyzing rigidity with pebble games

Full text

Pdf (241 KB)

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: Video and multimedia presentations table of contents

Pages 226-227

Year of Publication: 2008

ISBN:978-1-60558-071-5

Authors

Audrey Lee	University of Massachusetts Amherst, Amherst, MA, USA
Ileana Streinu	Smith College, Northampton, MA, USA
Louis Theran	University of Massachusetts Amherst, Amherst, MA, 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): 11, Downloads (12 Months): 60, 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.1377715 What is a DOI?

ABSTRACT

How many pair-wise distances must be prescribed between an unknown set of points, and how should they be distributed, to determine only a discrete set of possible solutions? These questions, and related generalizations, are central in a variety of applications. Combinatorial rigidity shows that in two-dimensions one can get the answer, generically, via an efficiently testable sparse graph property.

We present a video and a web site illustrating algorithmic results for a variety of rigidity-related problems, as well as abstract generalizations. Our accompanying interactive software is based on a comprehensive implementation of the pebble game paradigm.

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	Donald J. Jacobs , Bruce Hendrickson, An algorithm for two-dimensional rigidity percolation: the pebble game, Journal of Computational Physics, v.137 n.2, p.346-365, Nov. 1, 1997 [doi>10.1006/jcph.1997.5809]
	2	G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4:331--340, 1970.
	3	A. Lee and I. Streinu. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8):1425--1437, 2008.
	4	A. Lee, I. Streinu, and L. Theran. Finding and maintaining rigid components. In Proceeding of the Canadian Conference of Computational Geometry. Windsor, Ontario, 2005.
	5	A. Lee, I. Streinu, and L. Theran. The slider-pinning problem. In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG'07). Ottawa, Ontario, 2007.
	6	A. Lee, I. Streinu, and L. Theran. Graded sparse graphs and matroids. Journal of Universal Computer Science, 13(11):671--1679, 2007.
	7	I. Streinu and L. Theran. Sparse hypergraphs and pebble game algorithms. European Journal of Combinatorics, To appear.
	8	T.-S. Tay. Rigidity of multigraphs I: linking rigid bodies in n-space. Journal of Combinatorial Theory Series, B 26:95--112, 1984.
	9	T.-S. Tay. Linking (n -- 2)-dimensional panels in n-space II: (n -- 2, 2)-frameworks and body and hinge structures. Graphs and Combinatorics, 5:245--273, 1989.
	10	W. Whiteley. Some matroids from discrete applied geometry. In J. Bonin, J. G. Oxley, and B. Servatius, editors, Matroid Theory, volume 197 of Contemporary Mathematics, pages 171--311. American Mathematical Society, 1996.