Simple Polygonalizations

Can the number of simple polygonalizations of a set of $n$ points in the plane be computed in polynomial time? A simple polygonalization is a simple polygon whose vertices are the points.

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

Simple Polygonalizations

Coming soon

Organizer