Algorithms for Fence Design

摘要

A common task in automated manufacturing processes is to orient parts prior to assembly. We address sensorless orientation of a polygonal part on a conveyor belt by a sequence of stationary fences across this belt. Since fences can only push against the motion of the belt, it is a challenging problem to compute fence designs which orients a given part. In this paper, we give several polynomial-time, algorithms to compute fence designs which are optimal with respect to various criteria. We address both frictionless and frictional fences. We also compute modular fence designs in which the fence angles are restricted to a discrete set of angles instead of an interval.