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%).


( You need to enable Java to see this applet. )


Interested in the source? Get it here: matchfoursevenths.java.