Computational Complexity of Motion and Stability of Polygons

Other Titles


The ability to model physical objects and procedures accurately enough to predict their behavior without performing physical experimentation is a fundamental goal of robotics. This facility is prerequisite to offline modeling of assembly tasks, high level robotics languages, and automated assembly planning. This thesis defines and gives algorithms for two classes of physical modeling problems: Mobility problems and Stability problems. The Mobility problem for polygons is that of determining whether, in a configuration of non-intersecting polygons, one or more polygons can be moved (relative to some other polygon in the configuration) without causing intersection. Mobility is shown to be NP-hard. An upper bound for the mobility problem remains an open problem. Translational mobility is the problem of determining whether any polygons can be simultaneously moved by translations without causing intersection. Translational mobility is shown to be NP-complete. Infinitesimal mobility is the problem of determining whether there is a set of velocities for the polygons of the configuration such that no point of a polygon Pi that is in contact with another polygon Pj has a velocity directed towards the interior of Pj. Infinitesimal mobility can be viewed as an approximation to the mobility problem in that any configuration that is mobile is also infinitesimally mobile. Infinitesimal mobility is shown to be NP-complete. The Stability problem for polygons with mass is the problem of determining whether a configuration of polygons is at a static equilibrium point. The stability problem is considered for configurations of polygons with and without friction, and is shown to be NP-hard for both cases. An algorithm is given that distinguishes between configurations that are stable, unstable, and indeterminate. The ability to distinguish indeterminate configurations is important because indeterminate configurations arise when the model of an assembly is not accurate enough to determine whether the assembly is stable. Finally, a restricted class of configurations is developed, the determined configurations, for which a conservative stability problem can be solved in polynomial time. The determined configurations are a natural class in the sense that they preclude a type of contact that "seems unpredictable". If undetermined points are desired or unavoidable, the restricted stability problem can be solved in time exponential in the number of undetermined points in the configuration.

Journal / Series

Volume & Issue



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record