Disjoint Compatible Perfect Matching

Université Libre de Bruxelles
Computer Science Department
INFO-F420 Computational geometry
(professor Stefan Langerman)
Olivier Pirson OPiolivier_pirson_opi@yahoo.fr
March 23, 2017
Work in progress!


Some definitions

  • A planar straight line graph (PSLG) is a set of points in the plane, and a set of segments between some points such that there is no intersection.
  • A matching is a set of segments such that they have no point in common.
  • A matching is perfect iffif and only if each point is an end-point of one and only one segment.
  • Two matchings are disjoint iff their have no common segment.
  • Two matchings are compatible iff their union is without intersection.
  • transformation
  • canonical perfect matching

Experiment by yourself

1 Interactive application

Click in the two zones to add/remove point or segment (only one segment by point and without intersection).

Wait a moment above a button to bring up a short explanation tooltip.

  • :
  • :
  • :

2 Some explanations

You can add or remove points one by one, but only perfect matchings are useful. Isolated points are drawing in red. To remove a point, click on it. When a point is removed, all its segment are removed.

To add a segment, click to add the first point, then click to add the second point and the segment. It is impossible to add a segment to a point that already belongs to a segment, or to add a segment that intersects with an other segment. To remove a segment (and keeping its points), click to a first point and then to the second point.

If a matching is a canonical perfect matching then it is in a blue frame.

For two consecutive matchings in the list, common segments are in orange and segments that intersects between them are in red.

By default, all segments of the immediately previous and next matchings are draw in thin silver. An option permits to draw all segments that are in at least one matching in the list, or on the contrary to disable that and to draw only the segments of the matching.

For the matchings of the two interactive zones, some properties are displayed. Below that, some global properties between these two matchings are also displayed.

The matching of the left interactive zone is also displayed in the first position in the list. And the matching of the right interactive zone is displayed in the last position. Between them, are displayed all other perfect matchings or the intermediary perfect matchings to be a transformation.

Build all perfect matchings or build a shortest transformation are very expensive operations, so they are impossible with a lot of points.

3 Sources code

The interactive application was tested on Firefox 52.0 (requires ECMAScript/JavaScript 2015 6th and modern browser).

4 Known bugs

  • Build perfect matchings failed when points are vertical or horizontal aligned. (Because intersection test failed.)