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.
Publications:
- 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.
- 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:
-
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.
-
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,
karl@ee.washington.edu.
