The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
Lower Bounds for Geometrical and Physical Problems
Jurgen Sellen,
Pages. 1231-1253
Abstract
Contents 1. Introduction
2. Information processing by planar mechanisms
2.1. Coding of information
2.2. Transportation of information
2.3. Logical operations
2.4. Storage and copying of information
2.5. Sequential circuits and control sequences
2.6. Arithmetic on real numbers
3. Exponential lower bounds for kinematic problems
4. Motion planning under physical constraints
4.1. Undecidability results
4.2. Exponential lower bounds
4.3. A geometrical formulation of Turing computability
5. Future work
Key words motion planning, lower bounds, kinematic problems, dynamic problems, geometrical problems, collision-avoidability problem.
Mathmatical Subject Classification 68Q05, 03D10, 68Q25, 03D15, 68