- 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.
- canonical perfect matching
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.
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.
- Build perfect matchings failed when points are vertical or horizontal aligned. (Because intersection test failed.)
- Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, Mikio Kano, Alberto Márquez, David Rappaport, Shakhar Smorodinsky, Diane Souvaine, Jorge Urrutia, David R. Wood. Compatible Geometric Matchings. arXiv.org, 2nd version, January 16, 2008 Online PDF
- Greg Aloupis, Luis Barba, Stefan Langerman, Diane L. Souvaine. Bichromatic compatible matchings. arXiv.org, 3rd version, November 26, 2013 Online PDF
- Other assignments for the INFO-F420 Computational geometry course