The Curve Equipartition Problem
Costas Panagiotakis, George Georgakopoulos, Georgios Tziritas · 2005
In this paper, we analyze the general problem of a continuous curve partition into equal length segments, defined by any smooth distance metric, like the Euclidean distance. The goal is to locate N − 1 consecutive curve points, so that the curve can be divided into N equal length segments. First, it is proved that for any curve C and any number N there always exists at least one N-equipartition (EP) of C. The approach adopted for the proof can be used to compute at least one solution of the problem or all the solutions using a greedy version of this method. These methods have only theoretical value, as there appear algebraic expressions exponentially with increasing degree N . This can be explained by our proof that a version of the EP problem is NP-hard. So, the EP is possibly complete for the NP class. However, an O(N ) approximate proof based algorithm can solve the problem with high accuracy. Moreover, we propose two algorithms, an algorithm that computes approximately all the solutions and a steepest descent based method that converges to one of them. Some possible applications are also discussed.