Computing Form-Closure Configurations

We present the first output-sensitive algorithm for computing all placements of four (frictionless) points that put a polygonal part in form closure. Our efficient algorithm runs in O(n/sup 2+/spl epsiv//+K) time, where n is the number of vertices of the polygon, K is the description size of the set of form closure placements, and /spl epsiv/ is an arbitrarily small constant. The basis of our algorithm is a translation of the problem into geometric searching problems, which are solved with the use of efficient data structures. Our results can be extended to the problem of computing all placements of a line and two points that put a polygonal part in form closure. The resulting algorithm runs in O(n/sup 2/ log/sup 2/ n+K) time, where K is again the description size of the output.

Authors

• A. Frank van der Stappen
• Chantal Wentink
• Mark H. Overmars

Keywords

• Computer science
• Data structures
• Manufacturing
• Machining
• Inspection
• Resists
• Sufficient conditions
• Output Size
• Running Time
• Time Constant
• Contact Point
• Complex Solution
• Convex Hull
• Problem Of Finding
• Multiple Edges
• Left Edge
• Bottom Edge
• Points In Plane
• Set Of Contacts