For each vertex of a simple polygon P an integer valued weight is given. We consider the path p1, p2, ..., pk in P which is created according to the following strategy: p1 is a designated start vertex s and pi+1 is obtained by choosing the vertex with smallest weight among all vertices visible from pi and different from p1, p2, ..., pi. If there is no such vertex the path is finished. This path is called geometric lexicographic dead end (...) path. We shall prove the problem of determining whether a distinguished vertex t of P is on the geometric lexicographic dead end path or not to be P-complete. (shrink)

We consider the problem of quadrilaterizing an orthogonal polygon P, that is to decompose P into nonoverlapping convex quadrangles without adding new vertices. In this paper we present a CREW-algorithm for this problem which runs in O time using Θ processors if the rectangle decomposition of P is given, and Θ processors if not. Furthermore we will show that the latter result is optimal if the polygon is allowed to contain holes.

D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too.

First we give an overview about variants of visibility and related problems. Then we prove that some guarding and covering problems are NP-hard for ortho-polygons with holes, using a so-called vertex cover technique.

We show that given a simple Polygon P it is NP-hard to determine the smallest α ∈ [0, π] such that P can be illuminated by α-vertexlights, if we place exactly one α-vertexlight in each vertex of P.