One approach for computing simple polygons on a given point set in the plain

Abstract

We consider the problem of computing all possible simple polygons embrasing every point of a given finite point set in the plane. The developed approach is based on topological analysis of mutual visibility graphs of all free points and end points of a constructed chain. We found several new necessary conditions for existence of simple polygonal chains which are based on checking collocations of articulation points, bridges and biconnected components of such graphs. These conditions can be effectively applied for reducing trees of exhaustive search for all possible polygons on the given point set or for their random generation.