×
Frohmader, Andrew; Heaton, Alexander

Epsilon local rigidity and numerical algebraic geometry. (English) Zbl 1485.70001

J. Algebra Appl. 21, No. 1, Article ID 2250009, 21 p. (2022).
Summary: A well-known combinatorial algorithm can decide generic rigidity in the plane by determining if the graph is of Pollaczek-Geiringer-Laman type. Methods from matroid theory have been used to prove other interesting results, again under the assumption of generic configurations. However, configurations arising in applications may not be generic. We present Theorem 4.2 and its corresponding Algorithm 1 which decide if a configuration is \(\varepsilon\)-locally rigid, a notion we define. A configuration which is \(\varepsilon\)-locally rigid may be locally rigid or flexible, but any continuous deformations remain within a sphere of radius \(\varepsilon\) in configuration space. Deciding \(\varepsilon\)-local rigidity is possible for configurations which are smooth or singular, generic or non-generic. We also present Algorithms 2 and 3 which use numerical algebraic geometry to compute a discrete-time sample of a continuous flex, providing useful visual information for the scientist.

MSC:

70B15 Kinematics of mechanisms and robots
65D17 Computer-aided design (modeling of curves and surfaces)
14Q99 Computational aspects in algebraic geometry

Keywords:

numerical algebraic geometry; real algebraic geometry; rigidity; kinematics; mechanism mobility; homotopy continuation

Software:

Bertini; GitHub; HOM4PS; alphaCertified; tensegrity; PHCpack; HomotopyContinuation
PDF BibTeX XML Cite
\textit{A. Frohmader} and \textit{A. Heaton}, J. Algebra Appl. 21, No. 1, Article ID 2250009, 21 p. (2022; Zbl 1485.70001)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] T. Abbott, R. Barton and E. Demaine, Generalizations of Kempe’s Universality Theorem, Master’s Thesis, MIT (2009).
[2] Asimow, L. and Roth, B., The rigidity of graphs. II,J. Math. Anal. Appl.68(1) (1979) 171-190. · Zbl 0441.05046
[3] Aubry, P., Rouillier, F. and Safey El Din, M., Real solving for positive dimensional systems, J. Symb. Comput.34(6) (2002) 543-560. · Zbl 1046.14031
[4] D. J. Bates, J. D. Hauenstein, A. J. Sommese and C. W. Wampler, Bertini: Software for numerical algebraic geometry, bertini.nd.edu, https://doi.org/10.7274/R0H41PB5. · Zbl 1143.65344
[5] Bates, D. J., Sommese, A. J., Hauenstein, J. D. and Wampler, C. W., Numerically Solving Polynomial Systems with Bertini (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2013). · Zbl 1295.65057
[6] Blum, L., Cucker, F., Shub, M. and Smale, S., Complexity and Real Computation (Springer-Verlag, New York, 1998). With a foreword by Richard M. Karp. · Zbl 0872.68036
[7] Breiding, P. and Timme, S., Homotopycontinuation.jl: A package for homotopy continuation in julia, in Mathematical Software — ICMS 2018, eds. Davenport, J. H., Kauers, M., Labahn, G. and Urban, J. (Springer International Publishing, Cham, 2018), pp. 458-465. · Zbl 1396.14003
[8] Connelly, R., The rigidity of certain cabled frameworks and the second-order rigidity of arbitrarily triangulated convex surfaces,Adv. Math.37(3) (1980) 272-299. · Zbl 0446.51012
[9] R. Connelly and S. Guest, Frameworks, tensegrities and symmetry, preprint (2020). · Zbl 07437384
[10] Connelly, R. and Servatius, H., Higher-order rigidity — what is the proper definition?Discrete Comput. Geom.11(2) (1994) 193-200. · Zbl 0793.52005
[11] Gogu, G., Mobility of mechanisms: A critical review,Mech. Mach. Theory40(9) (2005) 1068-1097. · Zbl 1159.70312
[12] Goodman, J. E., O’Rourke, J. and Tóth, C. D. (eds.), Handbook of Discrete and Computational Geometry, 3rd edn., (CRC Press, Boca Raton, FL, 2018) [MR1730156].
[13] Hauenstein, J. D., Numerically computing real points on algebraic sets,Acta Appl. Math.125 (2012) 105-119. · Zbl 1269.65048
[14] Hauenstein, J. D. and Sommese, A. J., What is numerical algebraic geometry?J. Symb. Comput.79 (2017) 499-507, SI: Numerical Algebraic Geometry. · Zbl 1360.00098
[15] Hauenstein, J. D. and Sottile, F., Algorithm 921: AlphaCertified: Certifying solutions to polynomial systems, ACM Trans. Math. Softw.38(4) (2012), Article ID: 28, 20 pp. · Zbl 1365.65148
[16] A. Heaton, Nonlinear algebra via tensegrity structures, preprint (2019), arXiv:1908.08392.
[17] A. Heaton, Tensegrity, software (2020), https://github.com/alexheaton2/tensegrity.
[18] Holmes-Cerfon, M., Sticky-sphere clusters, Ann. Rev. Condens. Matter Phys.8(1) (2017) 77-98.
[19] M. Holmes-Cerfon, L. Theran and S. J. Gortler, Almost-rigidity of frameworks, preprint (2019). · Zbl 07405489
[20] Huber, B. and Sturmfels, B., A polyhedral method for solving sparse polynomial systems,Math. Comput.64(212) (1995) 1541-1555. · Zbl 0849.65030
[21] Juan, S. H. and Tur, J. M. M., Tensegrity frameworks: Static analysis review,Mech. Mach. Theory43(7) (2008) 859-881. · Zbl 1342.70013
[22] Lee, T. L., Li, T. Y. and Tsai, C. H., HOM4PS-2.0: A software package for solving polynomial systems by the polyhedral homotopy continuation method,Computing83(2-3) (2008) 109-133. · Zbl 1167.65366
[23] P. Olver, Lectures on moving frames, preprint (2012), https://www-users.math. umn.edu/olver/mf_/mfm.pdf. · Zbl 1235.53016
[24] Rouillier, F., Roy, M.-F. and Safey El Din, M., Finding at least one point in each connected component of a real algebraic set defined by a single equation, J. Complexity16(4) (2000) 716-750. · Zbl 1009.14010
[25] Seidenberg, A., A new decision method for elementary algebra,Ann. Math.60(2) (1954) 365-374. · Zbl 0056.01804
[26] Smale, S., Newton’s method estimates from data at one point, in The Merging of Disciplines \(:\) New Directions in Pure \(,\) Applied \(,\) and Computational Mathematics (Springer, New York, 1986), pp. 185-196. · Zbl 0613.65058
[27] Sommese, A. J. and Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (World Scientific, Singapore, 2005). · Zbl 1091.65049
[28] Strang, G., Computational Science and Engineering (Wellesley-Cambridge Press, Wellesley, MA, 2007). · Zbl 1194.65001
[29] Verschelde, J., Algorithm 795: Phcpack: A general-purpose solver for polynomial systems by homotopy continuation,ACM Trans. Math. Softw.25 (1999) 251-276. · Zbl 0961.65047
[30] Wampler, C. W., Hauenstein, J. D. and Sommese, A. J., Mechanism mobility and a local dimension test,Mech. Mach. Theory46(9) (2011) 1193-1206. · Zbl 1273.70004
[31] Whiteley, W., Matroids and rigid structures, in Matroid Applications, , Vol. 40 (Cambridge University Press, Cambridge, 1992), pp. 1-53. · Zbl 0768.05025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.