2025/09/22 by Tejel, Javier
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2509.17485
In the paper ``Lower bounds on the number of crossing-free subgraphs of KN'' (Computational Geometry 16 (2000), 211-221), it is shown that a double chain of n points in the plane admits at least Ω(4.642126305n) polygonizations, and it is claimed that it admits at most O(5.61n) polygonizations. In this note, we provide a proof of this last result. The proof is based on counting non-crossing path partitions for points in the plane in convex position, where a non-crossing path partition consists of a set of paths connecting the points such that no two edges cross and isolated points are allowed. We prove that a set of n points in the plane in convex position admits O^*(5.610718614n) non-crossing path partitions and a double chain of n points in the plane admits at least Ω(7.164102920n) non-crossing path partitions. If isolated points are not allowed, we also show that there are O^*(4.610718614n) non-crossing path partitions for n points in the plane in convex position and at least Ω(6.164492582n) non-crossing path partitions in a double chain of n points in the plane. In addition, using a particular family of non-crossing path partitions for points in convex position, we provide an alternative proof for the result that a double chain of n points admits at least Ω(4.642126305n) polygonizations.