Given two sets of points separated by a straight line, two points in the plane whose bisector
separates the sets are to be found. These two points can be taken as *representants*
of the two sets, and the *quality* of a chosen representant is measured as
the *radius* of the circle centered at the representant, containing its
corresponding set.

In other words, two circles of equal size have to be found so that their centers' bisector
separates the points into two predefined *clusters* and each circle encloses one cluster.
Such a circle is then called *Minimal Enclosing Circle* of its cluster or *MEC*.

Quick applet start (better read first) - click here:

Multiple clicks will start one instance each.

### Reference

This web site's intention is to present a short overview over the algorithm that solves the problem and to offer an applet-based tool to play around with and get an idea of this problem's inner connections.An abstract covering all details of this problem is available here:

**[TC03]**M. Abellanas, F. Hurtado, R. Klein, E. Langetepe, B. Palop, V. Sacristán.

*Bichromatic 2-center Problem.*Abstract 2003.

`2center`

(PostScript, gzipped, 68kB),
`2center`

(PDF unzipped, 348kB, for direct browsing using a PDF plugin)

### Overview

Initially, the situation depicts as shown in Figure 1: Two point sets, separated by an imaginary line, with their MECs. Without loss of generality, it is supposed that radius of*C*,

_{2}*r*, is >

_{2}_{=}

*r*, radius of

_{1}*C*. The goal is to find a bisector between two points

_{1}*c*and

_{1}*c*that is also a separating line

_{2}*and*the MECs with center at

*c*resp.

_{1}*c*.

_{2}
**Figure 1:** Two point sets, each with its convex hull and MEC.

For the algorithm it is important to differentiate between two cases:

- The two MECs do not intersect.
- They do.

- If this bisector does not intersect
*C*,_{2}*c*=_{1}*v*and_{1}*c*=_{2}*v*is already a solution for representants;_{2}*C*and its symmetric with respect to the bisector then are the two centers' MECs._{2} - If the bisector intersects with
*C*, take as new bisector the tangent to_{2}*C*parallel to the bisector. Then,_{2}*c*=_{2}*v*and its symmetric with respect to the new bisector is a solution for representants with corresponding minimal radius_{2}*r*._{2}

*r-region*and

*c*-umbrella of a point set have to be introduced (see Figure 2):

_{2}*r-region*(

*S*) is the locus of the points such that a circle centered at that point with radius

*r*contains the set

*S*.

*c*(

_{2}-umbrella*S*,

_{1}*S*) is the locus of all mirrored images of

_{2}*c*for all lines separating the sets

_{2}*S*and

_{1}*S*.

_{2}
**Figure 2:** *r-region*(*S*) (left) and
*c _{2}-umbrella*(

*S*,

_{1}*S*) (right).

_{2}Adapted from [TC03] fig. 2.

The follwing theorem was found (see [TC03] for proof):

**Theorem 1** (Figure 3) *If the *r_{2}*-region(*S_{1}*)
and the *c_{2}*-umbrella(*S_{1}*, *S_{2}*)
intersect, then *c_{2}*=*v_{2}* and any point *c_{1}* in the
intersection is a solution with optimal radius *r_{2}*.*

**Figure 3:** The *r _{2}*-region(

*S*) (red) intersects the

_{1}*c*-umbrella(

_{2}*S*,

_{1}*S*) (blue);

_{2}*c*lies in the intersection.

_{1}Taken from [TC03] fig. 3.

But what if the *r _{2}*-region(

*S*) and the

_{1}*c*-umbrella(

_{2}*S*,

_{1}*S*) do not intersect? [TC03] proves:

_{2}
**Lemma 2** (Figure 4) *If *c_{2}*=*v_{2}* is not a solution
for the radius *r_{2}* then the bisector for the optimal solutions
touches some of the two sets *S_{1}* or *S_{2}*.*

**Figure 4:** The bisector (orange) touches *S _{2}*, resulting in representants

*c*and

_{1}*c*with optimal radius.

_{2}*c*is

_{1}*not*equal to

*v*since MEC(

_{1}*S*) is smaller than

_{1}*C*.

_{1}

### Applet description

This is when the applet comes into play. It allows to move a bisector along the*visible chains*, between the

*inner tangents*, always touching a single point of a single set. By moving the bisector along, one can find by trial the smallest circle possible that is the optimal solution.

Click here to start an instance of the applet:

Multiple clicks will start one instance each.

The applet opens with an editor for points in the plane filling almost all of the frame.
A gray vertical line appears in the middle of the white. This is the *imaginary separating line*.
It's function is just to divide all drawed points into the two point sets
*S _{1}* and

*S*.

_{2}If points are set, one can zoom in and out by using the three

*zoom buttons*above.

At the right bottom a label informs about the currently calculated MEC's area.

All functions are completely controlled by mouse:

- To
*set a point*,*click left*on desired empty space. - To
*delete a point*,*click right*on the desired point. - To
*move a point*around,*click left*on the desired point*and hold while moving*the mouse. - To
*move the separating line*(or the*rotating bisector*, see below),*click left*on the line*and hold while moving*the mouse. - To
*rotate the separating line*,*click right*on the desired rotation point on the line*and hold while moving*the mouse up or down.

*right click*on

*empty space*brings up a

*context menu*. Here following functions are available:

*Clear points*does just that.*Run algorithm*allows disabling everything but editing points.- The next six options
*Show [...]*switch the corresponding graphical objects on or off. Note that some options make sense only if two or more points at the left or right side are set.

More details about these objects below. - If
*Activate rotating bisector*is active, an orange bisector appears and is movable by*clicking*on it*and moving*. This bisector can be moved within the limit that is given by the sets' inner tangents. - The remaining options are selectable only if the rotating bisector is active.

*Set active side...*switches the bisector to touch the left or right point set.

The next four options*Show [...]*switch the corresponding objects on or off.

#### Explanation of visible graphical objects

*Note:*The terms

*left*and

*right*refer to the orientation of graphic objects with respect to the

*separating line*shown in gray. If this line is rotated head over heels the directions seem to be inverted!

**Primary convex hulls**: The convex hulls of the left and right point set can be shown for better set recognition. Since points within the convex hulls do not have an impact on MEC calculation they can be removed; the primary convex hulls make recognizing these points easier.

**Visible chains**: Only bisectors between the

*inner tangents*derive candidates for the optimal MEC. The inner tangents also define the visible chains which are the part of the left and right convex hull that lie between the inner tangents. A bisector can only be tangent to a point of the visible chains.

**Left**/

**Right FPVD**: The

*Farthest Point Voronoi Diagram*of the left / right point set. These FPVDs are used in computation (see [TC03]).

**Left**/

**Right MEC**: The MEC of the left and right point set can be shown for comparation to the computed

*union MEC*.

**Rotating bisector**: The optimal solution corresponds to a bisector that is a tangent to the left or right point set and that lies within the bounds defined by the inner tangents. To find the optimal MEC, the bisector can be moved by mouse, while the resulting MEC's size is displayed in the bottom right label. Note that the global optimum is

*either*left

*or*right!

**Mirrored convex hull**/

**Mirrored FPVD**: The point set that is touched by the bisector is mirrored on it and the mirrored set's convex hull and MEC can be displayed for a visual check. Note: To show the mirrored point set itself, it is necessary to display either the Mirrored FPVD or the

*Union FPVD*!

**Union FPVD**: This FPVD is calculated as basis for the

*Union MEC*. See [TC03] for details.

**Union MEC**: The goal of the Bichromatic 2-center algorithm. Its area size is displayed in the bottom right label and is a direct quality measure. Its center is one of the two representants. Note that the other representant and its MEC (both symmetric with respect to the bisector) are

*not*shown!