Geometric under-constraints
Meera Sitharam, Heping Gao · 2008
We define and study exact, efficient representations of realization spaces Euclidean Distance Constraint Systems (EDCS). 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-edges or Cayley parameters. The set of realizable distance assignments to the chosen parameters yields a parametrized configuration space. We initialize a systematic and graded program of combinatorially characterizing graphs with configuration spaces of different geometry and algebraic complexity. Our notion of efficiency is based on the convexity and connectedness of the configuration space, as well as algebraic complexity of sampling realizations, i.e., sampling the configuration space and obtaining a realization from the sample (parametrized) configuration. Significantly, we give purely graph-theoretic, forbidden minor characterizations that capture the class of graphs that always admit efficient configuration spaces and the possible choices of representation parameters that yield efficient configuration spaces for a given graph. We completely characterize EDCS that have connected, convex and efficient 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 classical analytic and algebraic results related to positive semi-definiteness of Euclidean distance matrices, and Cayley-Menger conditions, with recent forbidden minor characterizations and algorithms related to realizability of EDCS. We further introduce a novel type of restricted edge contraction or reduction to a graph minor, a strategy that we anticipate will be useful in other situations. We study the class of 1-dof Henneberg-I graphs in order to take the next step in a systematic and graded program of combinatorial characterizations of efficient configuration spaces. We prove an algebraic theorem that makes combinatorial classification meaningful. We give the graph characterization according to the classification. We prove our results are tight and our definitions are robust. Our results have immediate CAD applications. We give preliminary results and conjectures for two natural extensions: which 2D EDCS have configuration space with at most two connected components and which 3D EDCS have connected configuration space. Finally, we discuss two application problems: characterizing configuration space of packing Zeolite and Helix. We give a surprising configuration space description theorem for Zeolite problem. We show that our novel simulation of Helix packing via geometric constraint solving provides quality and efficiency guarantees that other methods do not.