Match Four Sevenths
About the applet
This applet was written to visualize a result on a problem in
geometric matching. A geometric matching is an attempt to extend
the notion of graph-theoretical matchings for geometric graphs, by
using geometric objects (e.g. rectangles, squares, disks) to match
points on the plane. A geometric object matches two points if it
contains exactly those two points.
There are several problems related to the matching with geometric
objects. In this applet, we demonstrate how to find a matching that
covers at least 4/7 of the point set, using axis-aligned rectangles
as geometric objects.
Outline of the algorithm
In the first step of the algorithm, we partition the point set into
subsets that consist of points with the same x-coordinate. We then
process these subsets from left to the right. As soon as we can
match at least 4/7 of the points in the current subsets, we make a
cut disregarding those points for the rest of the processing. Since
every subset - except maybe the last - contains matchings that
cover at least 4/7 of the point sets, the overall matching covers
at least the same ratio (to be precise: for a set of n points, at
least 4/7n-5 points are matched).
Note that the result demonstrated on this page has subsequently been improved to a ratio of 2/3. This is tight due to the upper bound shown in Bereg et al. A link to the new algorithm will be added soon.
Exercise!
So, what leads to the ratio 4/7? The fact that we always make a
cut after at most 4 consecutive subsets. But that was just a hint.
Can you think of a point set with points that have 3 different
x-coordinates, for which only a ratio of 4/7 of the points can be
matched?
Check your solution.
Answer
A point set consisting of 7 points, of which at most 4 can be matched by rectangles.
A matching for the above point set covering 4/7 of the points.
Using the applet
Click on the canvas to add points to your point set.
If "Display lexicographical order" is marked, the points
will be sorted in lexicographical order, which is displayed by red
lines connecting the points. Clicking on "Match!" computes a
matching that is visualized as a set of yellow rectangles. The
vertical green lines demonstrate a cut being made after the last
subset. The text field will display the ratio of matched points to
total points (4/7 is approximately 57%).
Interested in the source? Get it here: matchfoursevenths.java.