ABSTRACT

This chapter surveys a series of recursive decomposition algorithms and culminates in an algorithm to solve the optimal Decomposition-recombination (DR-) planning problem in polynomial time for a broad class of minimally rigid or isostatic systems. To realize a geometric constraint system, it is crucial to perform recursive decomposition into locally rigid subsystems, and then apply the reverse process of recombining the subsystem solutions. A DR-plan is a recursive decomposition of a rigid constraint graph into rigid subgraphs. The two main goals of a DR-plan are that the solutions of the small subsystems can be recombined into a solution for the entire system and the subsystems should be geometrically meaningful. When dealing with a class for which optimal plans cannot be readily constructed, an algorithm can instead build DR-plans that satisfy other desirable properties. Given a geometric constraint system, a realization can naively be found by directly finding the zeros of the corresponding polynomial system.