For n vertices, it needs big-Omega of n to the three-halves entities to satisfy the problem in the interior since objects such as the Schönhardt polyhedron are not tetrahedralizable.
Agarwal proved that decision problem versions of this problem are NP- complete, and its unclear whether that version of this problem is in APX. Kooshesh and Moret combined Chazelle's triangulation algorithm with one proof of this problem to give a linear time algorithm for it. For n vertices, it needs big-Omega of n to the three-halves entities to satisfy the problem in the interior since objects such as the Schönhardt polyhedron are not tetrahedralizable. The exterior version of this problem is sometimes known as the fortress problem, and the original problem posed by Victor Klee can be proved by first showing that every polygon can be triangulated and then by making a 3-coloring of the triangulated polygon; this was the proof given by Steve Fisk, though the problem was originally proven by Chvátal, who showed it requires floor of n over 3 guards. For 10 points, name this problem that asks how many guards are needed to watch over the eponymous institution.
Agarwal proved that decision problem versions of this problem are NP- complete, and its unclear whether that version of this problem is in APX.
{Art Gallery} Problem