On fence design and the complexity of push plans for orienting parts

A common task in automated manufacturing processes is to orient parts prior to assembly. We consider sensorless orientation of a polygonal part by a sequence of push actions. We show that any polygonal part can be oriented by a sequence of fences placed along a conveyor belt, thereby settling a conjecture by Wiegley et al. [25], and present the first polynomial-time algorithm to compute the shortest such sequence. The algorithm is simple and runs in time O(n 3 log n), where n is the number of vertices of the part. Even though pathological parts can be constructed that require \Ω\Γ n) push actions, it turns out that almost all parts can be oriented using a small number of pushes. We deduce a new bound on the length of the shortest push plan that depends on the thinness -- or eccentricity -- of the part. The bound shows that only O(1) pushes are required for the large class of parts with non-square minimum-width bounding boxes. 1 Introduction Many automated manufacturing pro...