{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:56:11Z","timestamp":1777715771842,"version":"3.51.4"},"reference-count":22,"publisher":"SAGE Publications","issue":"9","license":[{"start":{"date-parts":[[2000,9,1]],"date-time":"2000-09-01T00:00:00Z","timestamp":967766400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2000,9]]},"abstract":"<jats:p>We address the problem of efficiently testing for linear unboundedness and its applications to translational assembly planning. We describe a new algorithm that performs the test by solving a single homogeneous system of equations followed by a single linear feasibility test. We show that testing for unboundedness is computationally at least as hard as these two subproblems. The new algorithm is the fastest known algorithm and is practical. We then present a framework for general translational assembly planning based on linear constraints. We show the relation of m-handed assembly planning to unboundedness testing and present a polynomial-time algorithm for m-handed assembly of polygonal part assemblies with no initially separated pairs of parts. For the general translational assembly\u2013planning problem, we present a new algorithm that uses unboundedness testing and a cell reduction technique to significantly increase the search efficiency. Experimental results of our implementation on a variety of planar and spatial assemblies demonstrate the practicality of the algorithms.<\/jats:p>","DOI":"10.1177\/02783640022067193","type":"journal-article","created":{"date-parts":[[2004,12,17]],"date-time":"2004-12-17T20:23:10Z","timestamp":1103314990000},"page":"817-834","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Linear Unboundedness Testing: Algorithm and Applications to                 Translational Assembly Planning"],"prefix":"10.1177","volume":"19","author":[{"given":"Fabian","family":"Schwarzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Achim","family":"Schweikard","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Technische Universit\u00e4t                         M\u00fcnchen, D-80290 M\u00fcnchen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leo","family":"Joskowicz","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, The Hebrew University,                         Jerusalem 91904, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2000,9,1]]},"reference":[{"key":"atypb1","unstructured":"Agarwal, P. K., de Berg, M., Halperin, D., and Sharir, M. 1996. Efficient generation of k-directional assembly sequences . Proc. 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), Atlanta, GA, pp. 122\u2013131 ."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00014419"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Ottmann, T. A., Soisalon-Soininen, E., and Wood, D. 1984. The complexity and decidability of SEPARATION . Proc. 11th Int. Colloquium on Autom. Lang. Prog. LNCS 172, 119\u2013127 .","DOI":"10.1007\/3-540-13345-3_10"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.2307\/2690292"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"Halperin, D.Latombe, J. C., and Wilson, R. H. 1998. A general framework for assembly planning: The motion space approach . Proc. of the 12th ACM Conference on Computational Geometry, Minneapolis, MN, pp. 9\u201318 .","DOI":"10.1145\/276884.276886"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Halperin, D., and Wilson, R. H. 1997. Assembly partitioning along simple paths: The case of multiple translations . Advanced Robotics 11: 127\u2013146 .","DOI":"10.1163\/156855397X00281"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"Hoffman, R. L. 1991. A common sense approach to assembly sequence planning. In Computer-Aided Mechanical Assembly Planning, ed. L. S. Homem de Mello and S. Lee, 289\u2013314. Boston: Kluwer .","DOI":"10.1007\/978-1-4615-4038-0_12"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Homem de Mello, L. S., and Lee, S., eds. 1991. Computer-Aided Mechanical Assembly Planning. Boston: Kluwer Academic .","DOI":"10.1007\/978-1-4615-4038-0"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"Huyn, T., Joskowicz, L., Lassez, C., and Lassez, J. L. 1991. Practical tools for reasoning about linear constraints . Fundamenta Informaticae 15: 3\u20134 .","DOI":"10.3233\/FI-1991-153-410"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1177\/027836499601500301"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Karmarkar, N. 1984. A new polynomial-time algorithm for linear programming. STOC, Washington, DC , pp. 302\u2013311.","DOI":"10.1145\/800057.808695"},{"key":"atypb12","unstructured":"Larsen, E., Gottschalk, S., Lin, M. C., and Manocha, D. 1999. Fast proximity queries with swept sphere volumes. Technical Report TR99-018, Department of Computer Science, University of North Carolina, Chapel Hill."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"Latombe, J. C. 1991. Robot Motion Planning. Boston: Kluwer Academic .","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., and Naeher, S. 1995. LEDA: A Platform for Combinatorial and Geometric Computing. Saarbr\u00fccken: Max-Planck-Institut f\u00fcr Informatik .","DOI":"10.1145\/204865.204889"},{"key":"atypb15","unstructured":"Ramkumar, G. D. 1998.\n                      Tracings and Their Convolution: Theory and Applications\n                      . Ph.D. thesis, Department of Computer Science, Stanford University."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00076-9"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189068"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574386"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"Stoer, J. 1976. Einf\u00fchrung in die Numerische Mathematik I. Berlin\/New York: Springer-Verlag .","DOI":"10.1007\/978-3-662-06864-9"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Toussaint, G. T. 1985. Movable separability of sets. In Computational Geometry, ed. G. T. Toussaint. New York: Elsevier .","DOI":"10.1016\/B978-0-444-87806-9.50018-9"},{"key":"atypb21","unstructured":"Wolter, J. D., and Trinkle, J. C. 1994. Automatic selection of fixture points for frictionless assemblies. Technical Report CS TR 94-017, Texas A&M University ."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"Wright, M. H. 1992. Interior methods for constrained optimization. In Acta Numerica, ed. A. Iserles. New York: Cambridge University Press .","DOI":"10.1017\/S0962492900002300"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022067193","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022067193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:19Z","timestamp":1777457779000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783640022067193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,9]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2000,9]]}},"alternative-id":["10.1177\/02783640022067193"],"URL":"https:\/\/doi.org\/10.1177\/02783640022067193","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,9]]}}}