Simple Polygonalizations

Let $S$ be a set of $n$ points in the plane in general position. A polygonalization of $S$ is a simple polygon whose vertex set is exactly $S$ . Determine whether the number of polygonalizations of $S$ can be computed in time polynomial in $n$ .

Download

Abstract

Given a planar point set, count the simple polygons whose vertex set is exactly the given set, and determine whether this count can be computed in polynomial time.

Background and progress

A general geometric separator framework yields an $n^{O(\sqrt n)}$ -time algorithm for counting polygonalizations [Marx and Miltzow, 2016]. Earlier work studied restricted polygonalizations such as monotone polygons [Zhu et al., 1996]; the polynomial-time counting problem remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p16.

Reference papers

Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problemsDániel Marx, Tillmann MiltzowProceedings of the 32nd International Symposium on Computational Geometry · 2016
Generating monotone polygons from unordered pointsBinhai Zhu, Ravi Sundaram, Jack Snoeyink, Joseph S. B. MitchellComputational Geometry: Theory and Applications · 1996