Smallest Color-Spanning ObjectsMotivated by questions in location planning, it is shown for a set of colored point sites in the plane how to compute the smallest - by perimeter or area - axis-parallel rectangle and the narrowest strip enclosing at least one site of each color.
Given a set of n point sites in the plane and k <= n
colors with each site associated one color, a region of the plane is
called color-spanning if it contains at least one point of each
The original motivation for computing such smallest color-spanning objects comes from location planning. Suppose there are k types of facilities, e.g. schools, post offices, supermarkets, modeled by n colored points in the plane, each type by its own color. One basic goal in choosing a residence location is in having at least one representative of each facility type in the neighborhood. A natural question is to ask for the smallest color-spanning circle or the smallest color-spanning axis-parallel square.
More information on Smallest Color-Spanning Objects,
including complexity and computation deliberations, can be found in this paper:
Smallest Color-Spanning Objects (PS, unzipped, 140K)
Smallest Color-Spanning Objects (PDF, unzipped, 401K)
How to use the appletsProvided using a browser with a properly installed Java-Plugin, the applet starts after clicking the following start button and pops up in a separate browser window that is resizable.
This applet is constructed to compute and display the smallest-by-area and the smallest-by-perimeter square of the current site set. These two rectangles are horizontally/vertically aligned along the x- and y-axis of the plane. Additionally, the global minima may be displayed; these rectangles are found in an arbitrary orientation.
The white area in the upper half is the plane editor. New point sites can be
set by clicking with the left mouse button on a free position. The color of new
sites can be set using the color buttons in the lower left panel named
Edit Color. To move a site, click-and-draw the desired site. To
delete a site, simply right-click it.
A right-click on empty space in the plane editor sets the rotation center, marked with a bold red circle.
Rotate panel, located in the applet's lower middle, is used
to control orientation of the whole plane, or the site set, respectively. For
manual rotation, use the
Right button. The
a rotation animation with adjustable rotation speed and rotation step size.
Speed and step size can be adjusted using the sliders below the rotation
In the lower right panel, called
Minimize, one can choose the
smallest color-spanning objects to display. Choice is between the previously
mentioned smallest-by-area and smallest-by-perimeter squares, and/or their