Open

Restricted Plane Sweep Triangulation (SWEEP)

Category: Logic

Input

An $n$-vertex polygon $P$ without holes.

Problem

Find the triangulation computed by the plane sweep triangulation algorithm.

Status

Open (Atallah, Callahan, and Goodrich [1]).

Definitions

See PST for a description of the algorithm.

Remarks

The problem of finding some arbitrary triangulation is in $\NC$ (Goodrich [2]). If the polygon is allowed to have holes, the problem is $\P$-complete [1]. See PST.

References

M. J. Atallah, P. Callahan, and M. T. Goodrich (1990). P-complete geometric problems.
M. T. Goodrich (1989). Triangulating a polygon in parallel.
Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.6.2.