language: en

[Submitted for review to Discrete and Computational Geometry, September 1997.]

On the Area Bisectors of a Polygon

Karl-Friedrich Bohringer
Cornell University
Bruce Randall Donald
Dartmouth College
Dan Halperin x
Tel Aviv University

Abstract 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 (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 Foundation under grants No. IRI-8802390, IRI-9000532, IRI-9201699, and by a Presidential Young Investigator award to Bruce Donald, in part by NSF/ARPA Special Grant for Experimental Research No. IRI-9403903, and in part by the Air Force Office of Sponsored Research, the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell laboratories. Work on this paper by Dan Halperin has been supported in part by an Alon Fellowship, by ESPRIT IV LTR Project No. 21957 (CGAL), by the USA-Israel Binational Science Foundation, and by the Hermann Minkowski - Minerva Center for Geometry at Tel Aviv University. A preliminary and abridged version of the paper appeared in]

[proc. 13th ACM Symp. on Computational Geometry, Nice, 1997, pp. 457-459.]

Robotics & Vision Laboratory, Department of Computer Science, Cornell University.
Author's current address:
ALPHA laboratory, Dept. of Ind. Eng. and Op. Research, University of California, Berkeley.
Email address: karl@IEOR.Berkeley.EDU.
Dept. of Computer Science, Dartmouth College,
6211 Sudikoff Laboratory, Hanover, NH 03755-3510.
brd@cs.dartmouth.edu,
x Department of Computer Science, Tel Aviv University,
Tel Aviv 69978, ISRAEL.
Email address: halperin@math.tau.ac.il.

[Part of the work on this paper was carried out while D.H. was at the Robotics Laboratory, Department of Computer Science, Stanford University.]