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: [applet could not be started]
Multiple clicks will start one instance each.


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)


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 C2, r2, is >= r1, radius of C1. The goal is to find a bisector between two points c1 and c2 that is also a separating line and the MECs with center at c1 resp. c2.

Figure 1: Two point sets, each with its convex hull and MEC.

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

  1. The two MECs do not intersect.
  2. They do.
In first case, it is easy to compute the bisector and MECs: Compute the bisector between the left and right MECs' center points. Then: In case of intersecting circles, things are quite more complex. The terms r-region and c2-umbrella of a point set have to be introduced (see Figure 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.
c2-umbrella(S1, S2) is the locus of all mirrored images of c2 for all lines separating the sets S1 and S2.

Figure 2: r-region(S) (left) and c2-umbrella(S1, S2) (right).
Adapted from [TC03] fig. 2.

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

Theorem 1 (Figure 3) If the r2-region(S1) and the c2-umbrella(S1, S2) intersect, then c2=v2 and any point c1 in the intersection is a solution with optimal radius r2.

Figure 3: The r2-region(S1) (red) intersects the c2-umbrella(S1, S2) (blue); c1 lies in the intersection.
Taken from [TC03] fig. 3.

But what if the r2-region(S1) and the c2-umbrella(S1, S2) do not intersect? [TC03] proves:

Lemma 2 (Figure 4) If c2=v2 is not a solution for the radius r2 then the bisector for the optimal solutions touches some of the two sets S1 or S2.

Figure 4: The bisector (orange) touches S2, resulting in representants c1 and c2 with optimal radius. c1 is not equal to v1 since MEC(S1) is smaller than C1.

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: [applet could not be started]
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 S1 and S2.
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:

A right click on empty space brings up a context menu. Here following functions are available:

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!