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

Literatur:

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