A near-quadratic algorithm for fence design

Published

Journal Article

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 part-manipulation problems as well. © 2004 Springer-Verlag New York, LLC.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Berretty, RP; Collins, AD

Published Date

  • January 1, 2005

Published In

Volume / Issue

  • 33 / 3

Start / End Page

  • 463 - 481

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/s00454-004-1148-9

Citation Source

  • Scopus