Analysis of the motion-planning problem for a simple two-link planar arm

A two-link planar robot arm is considered inside a planar polhygonal workspace. The configuration space of the arm is shown to have O(n³) components. Modelled on the Leven-Sharir algorithm, a connectivity graph is constructed, of size O(n³) in time O(n³log(n)). This graph can be used to solve any instance of the motion-planning problem for the arm.