Abstract
We define and study exact, efficient representations of realization spaces Euclidean Distance Constraint Systems (EDCS), which include Linkages and Frameworks. These are graphs with distance assignments on the edges (frameworks) or graphs with distance interval assignments on the edges. Each representation corresponds to a choice of non-edge (squared) distances or Cayley parameters. The set of realizable distance assignments to the chosen parameters yields a parametrized Cayley configuration space. Our notion of efficiency is based on the convexity and connectedness of the Cayley configuration space, as well as algebraic complexity of sampling realizations, i.e., sampling the Cayley configuration space and obtaining a realization from the sample (parametrized) configuration. Significantly, we give purely graph-theoretic, forbidden minor characterizations for 2D and 3D EDCS that capture (i) the class of graphs that always admit efficient Cayley configuration spaces and (ii) the possible choices of representation parameters that yield efficient Cayley configuration spaces for a given graph. We show that the easy direction of the 3D characterization extends to arbitrary dimension d and is related to the concept of d-realizability of graphs. Our results automatically yield efficient algorithms for obtaining exact descriptions of the Cayley configuration spaces and for sampling realizations, without missing extreme or boundary realizations. In addition, our results are tight: we show counterexamples to obvious extensions.
This is the first step in a systematic and graded program of combinatorial characterizations of efficient Cayley configuration spaces. We discuss several future theoretical and applied research directions.
In particular, the results presented here are the first to completely characterize EDCS that have connected, convex and efficient Cayley configuration spaces, based on precise and formal measures of efficiency. It should be noted that our results do not rely on genericity of the EDCS. Some of our proofs employ an unusual interplay of (a) classical analytic results related to positive semi-definiteness of Euclidean distance matrices, with (b) recent forbidden minor characterizations and algorithms related to d-realizability of graphs. We further introduce a novel type of restricted edge contraction or reduction to a graph minor, a “trick” that we anticipate will be useful in other situations.
Article PDF
Similar content being viewed by others
References
Alfakih, A.Y., Khandani, A., Wolkowicz, H.: Solving Euclidean distance matrix completion problems via semidefinite programming. Comput. Optim. Appl. 12, 13–30 (1999)
Bădoiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., Räcke, H., Ravi, R., Sidiropoulos, A.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In: SODA ’05: Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms, pp. 119–128 (2005)
Belk (Sloughter), M., Connelly, R.: Realizability of graphs. Discrete Comput. Geom. 37(2), 125–137 (2007)
Belk, M.: Realizability of graphs in three dimensions. Discrete Comput. Geom. 37(2), 139–162 (2007)
Biswas, P., Lian, T.-C., Wang, T.-C., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sen. Netw. 2(2), 188–220 (2006)
Blumenthal, L.M.: Theory and Applications of Distance Geometry. Oxford University, London (1953)
Borcea, C., Sitharam, M., Streinu, I.: The admissible distance polytope of partial 2-trees (in preparation)
Cayley, A.: A theorem in the geometry of position. Camb. Math. J. II, 267–271 (1841)
Connelly, R.: Generic global rigidity. Discrete Comput. Geom. 33(4), 549–563 (2005)
Crippen, G.M., Havel, T.F.: Distance Geometry and Molecular Conformation. Chemometrics Series, vol. 15. Research Studies Press, Somerset (1998)
Gao, H.: Geometric under-constraints. Ph.D. Thesis, University of Florida, Gainesville, FL (2008)
Gao, H., Sitharam, M.: Combinatorial classification of 2D underconstrained systems. In: Sung-il Pae and Hyungju Park (eds.), Proceedings of the Seventh Asian Symposium on Computer Mathematics (ASCM 2005), pp. 118–127 (2005)
Gao, H., Sitharam, M.: Characterizing 1-Dof Henneberg-I graphs with efficient configuration spaces. arXiv:0810.1997 [cs.CG]
Hausman, J.-C.: Geometric descriptions of polygon and chain spaces. Topology and Robotics. Am. Math. Soc. 438, 47–57 (2007)
Hoffmann, C.M., Lomonosov, A., Sitharam, M.: Decomposition of geometric constraints systems, part i: performance measures. J. Comput. 31(4), 367–408 (2001)
Hoffmann, C.M., Lomonosov, A., Sitharam, M.: Decomposition of geometric constraints systems, part ii: new algorithms. J. Symb. Comput. 31(4), 409–427 (2001)
Gortler, S.J., Healy, A.D., Thurston, D.P.: Characterizing generic global rigidity. arXiv:0710.0926v3 [math.MG]
Gower, T.: Weblog, http://gowers.wordpress.com/2007/09/11/what-might-an-expository-mathematical-wiki-be-like/
Graver, J.E., Servatius, B., Servatius, H.: Combinatorial Rigidity. Graduate Studies in Math. AMS, Providence (1993)
Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21(1), 65–84 (1992)
Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. J. Comb. Theory, Ser. B 94(1), 1–29 (2005)
Jackson, B., Jordán, T., Szabadka, Z.: Globally linked pairs of vertices in equivalent realizations of graphs. Discrete Comput. Geom. 35(3), 493–512 (2006)
Jacobs, D.J., Hendrickson, B.: An algorithm for two dimensional rigidity percolation: The pebble game. J. Comput. Phys. 137, 346–365 (1997)
Joan-Arinyo, R., Soto-Riera, A., Vila-Marta, S., Vilaplana-Pasto, J.: Transforming an under-constrained geometric constraint problem into a well-constrained one. In: Symposium on Solid Modeling and Applications 2003, pp. 33–44 (2003)
Kempe, A.B.: On a general method of describing plane curves of the nth degree by linkwork. Proc. Lond. Math Soc. 7, 213–216 (1876)
Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331–340 (1970)
Lee, A., Streinu, I., Theran, L.: Finding and maintaining rigid components, In: 17th Canadian Conference on Computational Geometry, pp. 219–222 (2005)
van der Meiden, H.A., Bronsvoort, W.F.: A constructive approach to calculate parameter ranges for systems of geometric constraints. Comput. Aided Des. 38(4), 275–283 (2006)
Menger, K.: New foundation for Euclidean geometry. Am. J. Math. 53, 721–745 (1931)
Owen, J.C., Power, S.C.: Algebraic solution for geometry from dimensional constraints. In: ACM Symp. Found. of Solid Modeling, Austin, TX, pp. 397–407 (1991)
Owen, J.C., Power, S.C.: The nonsolvability by radicals of generic 3-connected planar graphs. Trans. AMS 359(5), 2269–2303 (2006)
Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proc. 17th Allerton Conf. in Communications, Control, and Computing, pp. 480–489 (1979)
Schoenberg, I.J.: Metric spaces and positive definite functions. Trans. Am. Math. Soc. 44(3), 522–536 (1938)
Sitharam, M.: Graph based geometric constraint solving: problems, progress and directions. In: D. Dutta, R. Janardhan, and M. Smid (eds.), AMS-DIMACS Volume on Computer Aided Design (2005)
Sitharam, M., Peters, J., Gao, H., Kurnikova, M.: Exact and Efficient description of helix packing configuration space (in preparation)
man-Cho So, A., Ye, Y.: A semidefinite programming approach to tensegrity theory and realizability of graphs. In: SODA, pp. 766–775 (2006)
Zhang, G.F., Gao, X.S.: Well-constrained completion and decomposition for under-constrained geometric constraint problems. Int. J. Comput. Geom. Appl. 16(5–6), 461–478 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported in part by NSF Grants EIA 02-18435, CCF 04-04116, and a research gift from SolidWorks.
Rights and permissions
About this article
Cite this article
Sitharam, M., Gao, H. Characterizing Graphs with Convex and Connected Cayley Configuration Spaces. Discrete Comput Geom 43, 594–625 (2010). https://doi.org/10.1007/s00454-009-9160-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9160-8