 |
[]
[] []
|
|
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 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.
In first case, it is easy to compute the bisector and MECs: Compute the bisector
between the left and right MECs' center points. Then:
- 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.
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:
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.
A 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!
