Math @ Duke

Publications [#235477] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Berretty, RP; Collins, AD, A nearquadratic algorithm for fence design,
Discrete and Computanional Geometry, vol. 33 no. 3
(2005),
pp. 463481 [doi]
(last updated on 2018/10/23)
Abstract: A part feeder is a mechanism that receives a stream of identical parts in arbitrary orientations and outputs them oriented the same way. Various sensorless part feeders have been proposed in the literature. The feeder we consider consists of a sequence of fences that extend partway across a conveyor belt; a polygonal part P carried by the belt is reoriented by each fence it encounters. We present an O(m + n2 log3n)time algorithm to compute a sequence of fences that uniquely orients P, if one exists, where m is the total number of vertices and n is the number of stable edges of P. We reduce the problem to searching for a path in a state graph that has O(n 3) edges. By exploiting various geometric properties of this graph, we show that it can be represented implicitly and that a desired path can be computed in O(m + n2 log3n) time. We believe that our technique is quite general and could be applicable to other partmanipulation problems as well. © 2004 SpringerVerlag New York, LLC.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

