P252: Enumeration of all non-crossing perfect matchings on a given point set in the plane

P252: Enumeration of all non-crossing perfect matchings on a given point set in the plane

Input:

A fixed point set $P$.

Output:

All non-crossing perfect matchings on $P$.

Complexity:

$O(|P|^{3/2}tri(P) + |P|^{5/2}N)$ total time.

Comment:

$N$ is the number of solutions and $tri(P)$ is the number of triangulations of $P$.

Reference:

[Katoh2009a] (Bibtex)