On the Mating Between a Polygonal Curve and a Convex Polygon

Given a simple polygonal curve with m edges and a convex polygon with n edges lying respectively in two distinct parallel planes, we consider both the decision version and the optimization version of their mating problem. The decision version asks for whether a simple polyhedron can be constructed by a triangle connection between them without new vertices being inserted, and the optimization version is to obtain an optimal polyhedron if possible. This restricted curve-polygon mating problem is a natural variant of the previously studied polygon-polygon mating problem, whose computational complexity is still open even in the special case with one polygon being convex. In this paper, we first present an \(O(mn^4)\) -time dynamic-programming algorithm for both the decision version and the optimization version, and then present an \(O(mn+n^2)\) -time greedy algorithm for the decision version only. Additionally, we show that whether a polygonal curve is potentially matable with some convex polygon can be decided in linear time.