Non-crossing Hamiltonian paths and cycles in output-polynomial time.
D. Eppstein.
arXiv:2303.00147.
Proc. 39th International Symposium on Computational Geometry (SoCG 2023).
Leibniz
International Proceedings in Informatics (LIPIcs) 258, 2023,
pp. 29:1–29:16, doi:10.4230/LIPIcs.SoCG.2023.29.
Algorithmica 86: 3027–3053, 2024, doi:10.1007/s00453-024-01255-y.
Inaugural
Algorithmica best paper award, 2025.
For any point set, the numbers of non-crossing paths, non-crossing Hamiltonian paths, non-crossing surrounding polygons, and non-crossing Hamiltonian cycles can be bounded above and below by functions of two simple parameters: the minimum number of points whose deletion leaves a collinear subset, and the number of points interior to the convex hull. Because their bounds have the same form, the numbers of the two types of paths are bounded by polynomials of each other, as are the numbers of the two types of polygons. We use these relations to list non-crossing Hamiltonian paths and polygonalizations in time polynomial in the number of outputs.