Abstract

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.