The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields

Joint work with Bruce Donald and Danny Halperin.
We consider the family of 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 show that there are simple polygons with n vertices that have Omega(n²) combinatorially distinct area bisectors (matching the obvious upper bound - see figure), and we 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. These devices often exploit exotic actuation technologies such as MEMS (micro electro mechanical system) actuator arrays or transversely vibrating plates. 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.


  1. K.-F. Böhringer, B. R. Donald, D. Halperin, On the Area Bisectors of a Polygon, Submitted for review to Discrete and Computational Geometry , August 1997.
  2. K.-F. Böhringer, B. R. Donald, D. Halperin, The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields, 13th ACM Symposium on Computational Geometry , Nice, France (June 1997). 3 page communication.

    Also of interest:

  3. K.-F. Böhringer, B. R. Donald, N. C. MacDonald, G. T. A. Kovacs, J. W. Suh, Computational Methods for Design and Control of MEMS Micromanipulator Arrays, In IEEE Computer Science and Engineering, pages 17-29, January-March 1997.
  4. K.-F. Böhringer, B. R. Donald. N. C. MacDonald, Upper and Lower Bounds for Programmable Vector Fields with Applications to MEMS and Vibratory Plate Parts Feeders, In Mark Overmars and Jean-Paul Laumond, editors, Algorithms for Robotic Motion and Manipulation, pages 255-276, A. K. Peters, Wellesley, MA 02181, 1997.

Document created April 3 1997, last modified April 4 1997 by Karl-Friedrich Böhringer,