{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:05:50Z","timestamp":1765231550022},"reference-count":30,"publisher":"ASME International","issue":"3","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2004,9,1]]},"abstract":"<jats:p>In this paper, we apply a homotopy algorithm to the problem of finding points in a moving body that lie on specific algebraic surfaces for a given set of spatial configurations of the body. This problem is a generalization of Burmester\u2019s determination of points in a body that lie on a circle for five planar positions. We focus on seven surfaces that we term \u201creachable\u201d because they correspond to serial chains with two degree-of-freedom positioning structures combined with a three degree-of-freedom spherical wrist. A homotopy algorithm based on generalized linear products is used to provide a convenient estimate of the number of solutions of these polynomial systems. A parallelized version of this algorithm was then used to numerically determine all of the solutions.<\/jats:p>","DOI":"10.1115\/1.1760550","type":"journal-article","created":{"date-parts":[[2004,9,7]],"date-time":"2004-09-07T22:39:45Z","timestamp":1094596785000},"page":"226-234","update-policy":"http:\/\/dx.doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":24,"title":["Generalized Linear Product Homotopy Algorithms and the Computation of Reachable Surfaces"],"prefix":"10.1115","volume":"4","author":[{"given":"Hai-Jun","family":"Su","sequence":"first","affiliation":[{"name":"Department of Mechanical and Aerospace Engineering, University of California, Irvine, Irvine, CA\u200992697"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Michael","family":"McCarthy","sequence":"additional","affiliation":[{"name":"Department of Mechanical and Aerospace Engineering, University of California, Irvine, Irvine, CA\u200992697"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Layne T.","family":"Watson","sequence":"additional","affiliation":[{"name":"Departments of Computer Science and Mathematics, Virginia Polytechnic Institute and State University, Blacksburg, VA\u200924061"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2004,9,7]]},"reference":[{"key":"2019100610481333400_r1","unstructured":"Burmester, L., 1886, Lehrbuch der Kinematik, Verlag Von Arthur Felix, Leipzig, Germany."},{"key":"2019100610481333400_r2","unstructured":"Suh, C. H., and Radcliffe, C. W., 1978, Kinematics and Mechanism Design, John Wiley and Sons, New York."},{"key":"2019100610481333400_r3","unstructured":"Sandor, G. N., and Erdman, A. G., 1984, Advanced Mechanism Design: Analysis and Synthesis, Vol. 2, Prentice-Hall, Englewood Cliffs, NJ."},{"key":"2019100610481333400_r4","doi-asserted-by":"crossref","unstructured":"McCarthy, J. M., 2000, Geometric Design of Linkages, Springer-Verlag, New York.","DOI":"10.1115\/1.1334345"},{"key":"2019100610481333400_r5","doi-asserted-by":"crossref","unstructured":"Chen, P., and Roth, B., 1967, \u201cDesign Equations for Finitely and Infinitesimally Separated Position Synthesis of Binary Link and Combined Link Chains,\u201d ASME J. Eng. Ind., 91, pp. 209\u2013219.","DOI":"10.1115\/1.3591523"},{"key":"2019100610481333400_r6","unstructured":"Bottema, O., and Roth, B., 1979, Theoretical Kinematics, North Holland Press, NY."},{"key":"2019100610481333400_r7","unstructured":"McCarthy, J. M., 1990, An Introduction to Theoretical Kinematics, MIT Press, Cambridge, MA."},{"key":"2019100610481333400_r8","doi-asserted-by":"crossref","unstructured":"Liao, Q., and McCarthy, J. M., 2001, \u201cOn the Seven Position Synthesis of a 5-SS Platform Linkage,\u201d ASME J. Mech. Des., 123(1), pp. 74\u201379.","DOI":"10.1115\/1.1330269"},{"key":"2019100610481333400_r9","doi-asserted-by":"crossref","unstructured":"Morgan, A. P., Sommese, A. J., and Wampler, C. W., 1995, \u201cA Product-Decomposition Bound for Bezout Numbers,\u201d SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal., 32(4), pp. 1308\u20131325.","DOI":"10.1137\/0732061"},{"key":"2019100610481333400_r10","doi-asserted-by":"crossref","unstructured":"Verschelde, J. , 1999, \u201cAlgorithm 795: PHCpack: A Generalpurpose Solver for Polynomial Systems by Homotopy Continuation,\u201d ACM Trans. Math. Softw., 25(2), pp. 251\u2013276.","DOI":"10.1145\/317275.317286"},{"key":"2019100610481333400_r11","doi-asserted-by":"crossref","unstructured":"Wise, S. M., Sommese, A. J., and Watson, L. T., 2000, \u201cAlgorithm 801: POL_SYS PLP: A Partitioned Linear Product Homotopy Code for Solving Polynomial Systems of Equations,\u201d ACM Trans. Math. Softw., 26(1), pp. 176\u2013200.","DOI":"10.1145\/347837.347885"},{"key":"2019100610481333400_r12","doi-asserted-by":"crossref","unstructured":"Tsai, L.-W., and Morgan, A. P., 1985, \u201cSolving the Kinematics of the Most General Six- and Five-Degree-of-Freedom Manipulators by Continuation Methods,\u201d ASME J. Mech., Transm., Autom. Des., 107, pp. 189\u2013200.","DOI":"10.1115\/1.3258708"},{"key":"2019100610481333400_r13","doi-asserted-by":"crossref","unstructured":"Wampler, C. W., Morgan, A. P., and Sommese, A. J., 1990, \u201cNumerical Continuation Methods for Solving Polynomial Systems Arising in Kinematics,\u201d ASME J. Mech. Des., 112(1), pp. 59\u201368.","DOI":"10.1115\/1.2912579"},{"key":"2019100610481333400_r14","unstructured":"Sommese, A. J., Verschelde, J., and Wampler, C. W., 2002, \u201cAdvances in Polynomial Continuation for Solving Problems in Kinematics,\u201d Proc. 2002 ASME Design Engineering Technical Conferences, paper no. DETC2002\/MECH-34254, Sept. 29-Oct. 2, Montreal, Canada."},{"key":"2019100610481333400_r15","doi-asserted-by":"crossref","unstructured":"Lee, E., and Mavroidis, D., 2002, \u201cSolving the Geometric Design Problem of Spatial 3R Robot Manipulators Using Polynomial Homotopy Continuation,\u201d ASME J. Mech. Des., 124(4), pp. 652\u2013661.","DOI":"10.1115\/1.1515796"},{"key":"2019100610481333400_r16","doi-asserted-by":"crossref","unstructured":"Watson, L. T., Sosonkina, M., Melville, R. C., Morgan, A. P., and Walker, H. F., 1997, \u201cAlgorithm 777: HOMPACK90: A suite of Fortran 90 codes for globally convergent homotopy algorithms,\u201d ACM Trans. Math. Softw., 23(4), pp. 514\u2013549.","DOI":"10.1145\/279232.279235"},{"key":"2019100610481333400_r17","doi-asserted-by":"crossref","unstructured":"Wampler, C. , 1994, \u201cAn Efficient Start System for Multi-Homogeneous Polynomial Continuation,\u201d Numer. Math., 66, pp. 517\u2013523.","DOI":"10.1007\/BF01385710"},{"key":"2019100610481333400_r18","doi-asserted-by":"crossref","unstructured":"Allison, D. C. S., Harimoto, S., and Watson, L. T., 1989, \u201cThe Granularity of Parallel Homotopy Algorithms for Polynomial Systems of Equations,\u201d Int. J. Comput. Math., 29, pp. 21\u201337.","DOI":"10.1080\/00207168908803746"},{"key":"2019100610481333400_r19","doi-asserted-by":"crossref","unstructured":"Allison, D. C. S., Chakraborty, A., and Watson, L. T., 1989, \u201cThe Granularity of Parallel Homotopy Algorithms for Polynomial Systems of Equations,\u201d J. Supercomputing, 3, pp. 5\u201320.","DOI":"10.1007\/BF00129645"},{"key":"2019100610481333400_r20","doi-asserted-by":"crossref","unstructured":"Chakraborty, A., Allison, D. C. S., Ribbens, C. J., and Watson, L. T., 1991, \u201cNote on Unit Tangent Vector Computation for Homotopy Curve Tracking on a Hypercube,\u201d Parallel Comput., 17, pp. 1385\u20131395.","DOI":"10.1016\/S0167-8191(05)80005-5"},{"key":"2019100610481333400_r21","doi-asserted-by":"crossref","unstructured":"Chakraborty, A., Allison, D. C. S., Ribbens, C. J., and Watson, L. T., 1993, \u201cThe Parallel Complexity of Embedding Algorithms for the Solution of Systems of Nonlinear Equations,\u201d IEEE Trans. Parallel Distrib. Systems, 4, pp. 458\u2013465.","DOI":"10.1109\/71.219760"},{"key":"2019100610481333400_r22","unstructured":"Gropp, W., Lusk, E., and Skjellum, A., Using MPI, Portable Parallel Programming with the Message-Passing Interface, second edition, The MIT Press, Cambridge, MA."},{"key":"2019100610481333400_r23","unstructured":"Craig, J. J., 1989, Introduction to Robotics, Mechanics and Control, Addison Wesley, Reading, MA."},{"key":"2019100610481333400_r24","doi-asserted-by":"crossref","unstructured":"Innocenti, C. , 1995, \u201cPolynomial Solution of the Spatial Burmester Problem,\u201d ASME J. Mech. Des., 117, pp. 64\u201368.","DOI":"10.1115\/1.2826118"},{"key":"2019100610481333400_r25","doi-asserted-by":"crossref","unstructured":"Su, H.-J., Wampler, C., and McCarthy, J. M., 2004, \u201cGeometric Design of Cylindric PRS Serial Chains,\u201d ASME J. Mech. Des., (in press).","DOI":"10.1115\/DETC2003\/DAC-48816"},{"key":"2019100610481333400_r26","doi-asserted-by":"crossref","unstructured":"Neilsen, J. and Roth, B., 1995, \u201cElimination Methods for Spatial Synthesis,\u201d Computational Kinematics, (eds. J. P. Merlet and B. Ravani), 40, pp. 51\u201362, Kluwer Academic Publishers.","DOI":"10.1007\/978-94-011-0333-6_6"},{"key":"2019100610481333400_r27","doi-asserted-by":"crossref","unstructured":"Su, H.-J., and McCarthy, J. M., 2003, \u201cKinematic Synthesis of a RPS Serial Chains,\u201d Proceedings of the ASME Design Engineering Technical Conference, September 2\u20136, 2003, Chicago, Il.","DOI":"10.1115\/DETC2003\/DAC-48813"},{"key":"2019100610481333400_r28","doi-asserted-by":"crossref","unstructured":"Kim, H. S., and Tsai, L. W., 2002, \u201cKinematic Synthesis of Spatial 3-RPS Parallel Manipulators,\u201d Proc. ASME Des. Eng. Tech. Conf. paper no. DETC2002\/MECH-34302, Sept. 29-Oct. 2, 2002, Montreal, Canada.","DOI":"10.1115\/DETC2002\/MECH-34302"},{"key":"2019100610481333400_r29","unstructured":"Gao, T., Li, T. Y., and Wu, M., 2003, \u201cMixedVol: A Software Package for Mixed Volume Computation,\u201d preprint, submitted to ACM Transactions on Math. Sofware, August."},{"key":"2019100610481333400_r30","unstructured":"Su, H.-J., 2004, \u201cComputer Aided Synthesis of Constrained Serial and Parallel Robots,\u201d Ph.D. Dissertation, Department of Mechanical and Aerospace Engineering, University of California, Irvine."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/4\/3\/226\/5670999\/226_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/4\/3\/226\/5670999\/226_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T14:33:09Z","timestamp":1624631589000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/4\/3\/226\/445333\/Generalized-Linear-Product-Homotopy-Algorithms-and"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9,1]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,9,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.1760550","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"value":"1530-9827","type":"print"},{"value":"1944-7078","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9,1]]}}}