{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:51Z","timestamp":1787340651035,"version":"build-2736575974"},"reference-count":7,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,5]]},"abstract":"<jats:p>The mover\u2019s problem is the following: can an object in 3-dimensional space be moved from one given position to another while avoiding obstacles? It is known that the general version of this problem involving objects with movable joints is PSPACE hard, even for a simple tree-like structure moving in a 3-dimensional region. In this paper, we investigate a 2-dimensional mover\u2019s problem in which the object is a robot arm with an arbitrary number of joints. In particular, we give a polynomial time algorithm for moving an arm confined within a circle from one given configuration to another. We also give a polynomial time algorithm for moving the arm from its initial position to a position in which the end of the arm reaches a given point within the circle. Finally, we show that 148 circles suffice to cover the boundary of the reachable region of a joint in an arm enclosed in a circle and that the boundary can be computed in polynomial time.<\/jats:p>","DOI":"10.1137\/0214025","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"315-333","source":"Crossref","is-referenced-by-count":37,"title":["On the Movement of Robot Arms in 2-Dimensional Bounded Regions"],"prefix":"10.1137","volume":"14","author":[{"given":"John","family":"Hopcroft","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deborah","family":"Joseph","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sue","family":"Whitesides","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R2","unstructured":"J. E. Hopcroft, D. A. Joseph, S. H. Whitesides,  Determining points of a circular region reachable by joints of a robot arm, Technical Report, TR82-516, Computer Science Department, Cornell Univ., Ithaca, NY,  1982, October"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308589"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J. Reif,  Complexity of the mover's problem and generalization,  Proc. 20th IEEE Symposium on the Foundations of Computer Science,  1979,  421\u2013427","DOI":"10.1109\/SFCS.1979.10"},{"key":"R6","unstructured":"J. T. Schwartz, M. Sharir,  On the \u201cpiano movers\u201d problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers, TR39, Dept. Computer Science, New York Univ., New York,  1981, October"},{"key":"R7","unstructured":"J. T. Schwartz, M. Sharir,  On the \u201cpiano movers\u201d problem II. General techniques for computing topological properties of real algebraic manifolds, TR41, Dept. Computer Science, New York Univ., New York,  1982, February"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:45Z","timestamp":1787337765000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,5]]},"references-count":7,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,5]]}},"alternative-id":["10.1137\/0214025"],"URL":"https:\/\/doi.org\/10.1137\/0214025","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,5]]}}}