Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235618] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Berretty, R-P; Collins, AD, A near-quadratic algorithm for fence design, Springer Tracts in Advanced Robotics, vol. 7 STAR (2004), pp. 347-362, ISSN 1610-7438 [doi]
    (last updated on 2017/12/18)

    A part feeder is a mechanism that receives a stream of identical parts in arbitrary orientations and putputs 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 + n 2log 3 n)-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. As in [3], 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 the state graph, we show that it can be represented implicitly and a desired path can be found in O(m + n 2log 3 n) time. Our technique is quite general and is applicable to other part manipulation problems. © 2004 Springer-Verlag.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320