Geometry / Triangulation (Bibtex)

P81: Enumeration of all regular triangulations

Input:

$n$ points.

Output:

All 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.

Reference:

[Masada1996] (Bibtex)

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.

Reference:

[Masada1996] (Bibtex)

P323: Enumeration of all triangulations of a point set

Input:

A point set $P$.

Output:

All triangulations of $P$.

Complexity:

$O(|P|N)$ total time and $O(|P|)$ space.

Comment:

$N$ is the number of solutions.

Reference:

[Avis1996] (Bibtex)

P112: Enumeration of all triangulations in general dimensions

Input:

Points.

Output:

All triangulations.

Complexity:

See the paper.

Comment:

This algorithm uses the enumeration algorithm for maximal independent sets.

Reference:

[Takeuchi] (Bibtex)

P113: Enumeration of all regular triangulations in general dimensions

Input:

Points.

Output:

All regular triangulations.

Complexity:

See the paper.

Comment:

This algorithm uses the enumeration algorithm for maximal independent sets.

Reference:

[Takeuchi] (Bibtex)

P297: Enumeration of all triangulation paths of a point set

Input:

A point set $P$.

Output:

All triangulation paths of $P$.

Complexity:

$O(N|P|^3\log |P|)$ time and $O(|P|)$ space.

Comment:

$N$ is the number of solutions.

Reference:

[Dumitrescu2001] (Bibtex)

P19: Enumeration of all triangulations

Input:

A set $S$ of $n$ points in the general position in the plane.

Output:

all the triangulations whose vertex set is $S$ and edge set includes the convex hull of $S$.

Complexity:

$O(\log\log n)$ time per triangulation and linear space.

Comment:

Whether there is the algorithm that outputs all triangulations in constant time delay?

Reference:

[Bespamyatnikh2002] (Bibtex)

P279: Enumeration of all pseudotriangulations of a finite point set

Input:

A point set $S$ of size $n$.

Output:

All pointed pseudotriangulations of $S$.

Complexity:

$O(\log n)$ time per solution with linear space.

Comment:

Reference:

[Bereg2005] (Bibtex)

P265: Enumeration of all pseudotriangulations of a point set

Input:

A point set $P$.

Output:

All pseudotriangulations of $P$.

Complexity:

$O(n)$ time per pseudotriangulation.

Comment:

$n$ is the number of points in $P$.

Reference:

[Bronnimann2006a] (Bibtex)

P171: Enumeration of all triangulations of a convex polygon of $n$ vertices with numbered

Input:

A convex polygon $P$ with $n$ vertices that are numbered.

Output:

All triangulations of $P$.

Complexity:

$O(1)$ time per triangulation and $O(n)$ space.

Comment:

Reference:

[Parvez2009] (Bibtex)

P172: Enumeration of all triangulations of a convex polygon of $n$ vertices

Input:

A convex polygon $P$ with $n$ vertices that are not numbered.

Output:

All triangulations of $P$.

Complexity:

$O(n^2)$ time per triangulation and $O(n)$ space.

Comment:

Reference:

[Parvez2009] (Bibtex)