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
[1] E. D. Demaine, J. S. B. Mitchell, J. O'Rourke, "The Open Problems Projects," http://cs.smith.edu/. [Online]. Available: http://cs.smith.edu/~orourke/TOPP/. [Accessed: Oct. 25, 2015].
[2] ComPoSe, Eurocores-EuroGIGA, "Combinatorics of Point Sets and Arrangements of Objects," http://www.eurogiga-compose.eu. [Online]. Available: - http://www.eurogiga-compose.eu/about.php. [Accessed: Oct. 25, 2015].
[3] Rectilinear Crossing Number, "Rectilinear Crossing Number Project," http://dist.ist.tugraz.at [Online]. Available: http://dist.ist.tugraz.at/cape5/. [Accessed: Oct. 25, 2015].
[4] V. Muravitskiy, V. Tereshchenko, "Generating a simple polygonalizations," In Proceedings of 15th International Conference on Information Visualisation, pp.502-506, Jul. 2011.
[5] Andriy Fisunenko, "Generation of simple polygons by cutting out and building up convex hulls". Bulletin of Taras Shevchenko National University of Kyiv, Series Physics & Mathematics, vol. Spetsvypusk, pp.190-193., Dec. 2013.
[6] T. Auer, M. Held, "Heuristics for the generation of random polygons," In Proceedings of the 8th Canadian Conference on Computational Geometry, Ottawa, Ontario, pp.38-43, Jan. 2006.
[7] J. A. Shuffelt, H. J. Berliner, "Generating Hamiltonian circuits without backtracking from errors," Theoretical Computer Science Journal, vol. 132 (s 1-2), pp.347-375, Sep. 1994.