Geometric algorithms for trap design

Abstract

Geometric algorithms have successfully been applied to solve or give insight into problems in robotic manipulation. In this paper, we present a framework to filter polygonal parts on a track. The filter consists of a polygonal hole in the track; we refer to the filters as traps. For an n-sided polygonal part and an m-sided polygonal trap, we give an O((nm(n + m)) 1+ffl ) algorithm to decide whether the part in a specific orientation will safely move across the trap or will fall through the trap and thus be filtered out. Furthermore, we show how to design various parameterized traps, ranging from simple gaps to arbitrary polygons which will filter out all but one of the different stable orientations of a given part. 1 Introduction Geometric algorithms are important tools to solve or give insight into real world problems. In this paper, we transform the problem of designing traps into geometric problems, which are then solved with the use of techniques from computational geometry. ...