Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Movement problems for 2-dimensional linkages
Hopcroft J. (ed), Joseph D., Whitesides S. SIAM Journal on Computing13 (3):610-629,1984.Type:Article
Date Reviewed: Feb 1 1985

This is a beautiful paper with two highly original results. First, it is shown that a planar linkage can be forced to stay inside a region by the addition of a polynomial number of new links (polynomial in the number of original links and the number of sides of the region). Second, the reachability question for planar linkages is proved to be PSPACE-hard. This means that for a given initial configuration of an arbitrary linkage, the question of whether it can be moved so that a particular joint in that linkage reaches a predetermined point of the plane is PSPACE-hard.

The essential technique used throughout this paper is to construct complex linkages by putting together simpler special-purpose linkages, some of these simpler linkages date from the late 1800s and give this paper a lot of mathematical charm and elegance. In summary, this is a welcome addition to the recent results in “robotics from a complexity point of view.”

Reviewer:  V. Akman Review #: CR108816
Bookmark and Share
 
Robotics (I.2.9 )
 
 
Motion (I.2.10 ... )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Robotics": Date
Robot motion planning with uncertainty in control and sensing
Latombe J. (ed), Lazanas A., Shekhar S. Artificial Intelligence 52(1): 1-47, 1991. Type: Article
Oct 1 1992
Dictionary of robot technology in four languages: English, German, French, Russian
Bürger E., Korzak G., Elsevier North-Holland, Inc., New York, NY, 1986. Type: Book (9789780444995193)
Mar 1 1988
Navigation and world modelling for a mobile robot: a progress report
Crowley J.  CAD and robotics in architecture and construction (, Marseilles, France,2241986. Type: Proceedings
Jan 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy