Smallest Color-Spanning Objects

Motivated 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 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 (PDF, unzipped, 401K)

How to use the applets

Provided 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.

[applet could not be started]

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.


[1]:Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, Belén Palop, Vera Sacristán. Smallest Color-Spanning Objects.