A P‐Completeness Result for Visibility Graphs of Simple Polygons

For each vertex of a simple polygon P an integer valued weight is given. We consider the path p₁, p₂, ..., p_k in P which is created according to the following strategy: p₁ is a designated start vertex s and p_i+1 is obtained by choosing the vertex with smallest weight among all vertices visible from p_i and different from p₁, p₂, ..., p_i. 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.