GOALS AND PURPOSES

The goal of this project was to design, implement, and experiment with algorithms for covering a convex polygon with a minimal number of fixed-radius circles. Our motivation was from the area of mobile robot navigation, where many applications employ sensors or transmitters embedded in the environment. In some hospitals, for example, robots deliver prescriptions to nurses' stations, navigating the hallways with the aid of tiny radio transmitters installed on the ceilings. The main problem we investigated this year was how to cover the environment with overlapping circles, each circle enclosing the area covered by one device (a transmitter or sensor).

STUDENTS AND MENTOR INVOLVED

The two undergraduate women involved were Joanna Blanding and Xinmei Cai. Both students worked with Professor Amy Briggs during their senior year at Middlebury College. The student work was primarily implementation work in Java. Xinmei also wrote her senior thesis on some closely related problems in art gallery theory.

METHODS AND PROCESSES

At the start of the project we studied several different approaches to the circle placement problem. The two most promising algorithms we started with were a grid-based and a greedy approach. Our initial idea for the grid-based approach worked as follows: impose a regular grid of transmitter positions on the plane such that the covering of the plane is optimal, that is, so that the entire plane is covered and the area of overlap between circles is minimized. Place the polygon (representing the environment) on the grid so as to minimize the number of grid points (transmitters) contained inside the polygon. The greedy approach was to start at a vertex of the polygon and move around the boundary placing circles. In the interior region that remains, repeatedly march around the boundary placing points, working toward the center until the entire polygon is covered. We worked together to devise a modified version of the grid-based approach that was simple and efficient, and then implemented our new algorithm. Joanna and Xinmei worked together to design the low-level classes and primitives as well as the overall applet. They refined the applet with added functionality throughout the year.

CONCLUSIONS AND RESULTS ACHIEVED

The Java applet developed by the students allows the user to mouse in a polygon, rotate it to align any edge with the horizontal, and then cover the polygon with circles and report the number used. Any circles with centers outside the boundary of the polygon can be moved to put their centers on the boundary. The applet is available at www.middlebury.edu/~math/Projects/sensor. Currently we are using the applet to perform experiments on large numbers of random polygons to evaluate the algorithm's performance and its dependence on circle radius, polygon size, and length of the starting edge.