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
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.
ReferenceThis 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)
OverviewInitially, 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:
- The two MECs do not intersect.
- They do.
- If this bisector does not intersect C2, c1=v1 and c2=v2 is already a solution for representants; C2 and its symmetric with respect to the bisector then are the two centers' MECs.
- If the bisector intersects with C2, take as new bisector the tangent to C2 parallel to the bisector. Then, c2=v2 and its symmetric with respect to the new bisector is a solution for representants with corresponding minimal radius r2.
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 descriptionThis 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
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:
- 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.
- 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 objectsNote: 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!