P82: Enumeration of all spanning regular triangulations
P82: Enumeration of all spanning regular triangulations
Input:
$n$ points.
Output:
All spanning regular triangulations of given points in $(d-1)$-dimensional space.
Complexity:
$O(dsLP(r, ds)T')$ time and $O(ds)$ space.
Comment:
$s$ is the upper bound of the number of simplcies contained in one regular triangulation, $LP(r, ds)$ denotes the time complexity of solving linear programming problem with $ds$ strict inequality constraints in $r$ variables, and $T'$ is the number of regular triangulations.