 |
|
|
|
|
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
color.
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 (PS, g-zipped, 51K)
Smallest Color-Spanning Objects (PDF, unzipped, 401K)
Smallest Color-Spanning Objects (PDF, g-zipped, 117K)
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.
The 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 Left and Right button. The
auto-rotation buttons Auto-Left and Auto-Right provide
a rotation animation with adjustable rotation speed and rotation step size.
Speed and step size can be adjusted using the sliders below the rotation
buttons.
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
global equivalents.