2026-07-20T11:15:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17879 2024-03-06T11:00:36Z ddc:004 open_access

Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time Eppstein, David polygonalization non-crossing structures output-sensitive algorithms We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Eppstein 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.29 urn:nbn:de:0030-drops-178790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.29 eng https://creativecommons.org/licenses/by/4.0/legalcode