On the Area Bisectors of a Polygon

We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different partitionings of the vertices of P . We derive an algebraic characterization of area bisectors. We then show that there are simple polygons with n vertices that have \Omega\Gamma n 2 ) combinatorially distinct area bisectors (matching the obvious upper bound), and present an output-sensitive algorithm for computing an explicit representation of all the bisectors of a given polygon. Our study is motivated by the development of novel, flexible feeding devices for parts positioning and orienting. The question of determining all the bisectors of polygonal parts arises in connection with the development of efficient part positioning strategies when using these devices. Work on this paper by Karl-Friedrich Bohringer and Bruce Randall Donald has been supported in part by the National Science..