There are finite number of possibly overlapped points (say 100) on a finite length line, how to partition the line into finite number of segments (say 12), each has as same number of points as possible? (note: the number of unique values of points may or may not more than the number of segments, therefore empty segments are allowed.)
UPDATE: Segments need to have similar amount of points. Say total 100 points, required to partition into 10 segments, then the ideal solution should be 10 points on each segment.
Q1, It might have multiple solutions. then how to choose the best solution? is using standard deviation to on the numbers of points of each segments a good measure?
Q2, It's relative easy to generate solutions by firstly segmenting points by unique values, then parametize boundaries (kind of local optimization). Is it true that local optimized solutions are also globally optimized?
UDATE "Optimization": since it's say points [1,2,2,2,3,3,4], required to partitioned into 3 segments. Then possible solutions are:
a) [1], [2,2,2,3,3], [4]
b) [1], [2,2,2], [3,3,4]
It's possible that solution b) is an optmization of solution a), if b) is not generated via the primary algorithm.
Q3, How to optimize a candidate solution globally?
Q4, Is there an algorithm?
Even assuming no points are identical, the problem is not well specified. Let's assume they are all different for now. First, sort the points in order along the line. You can then partition the list however you want. If you have 100 points, do you want 4 segments of 25, 10 segments of 10, or what?
It is not clear what kind of optimization you are talking about. As long as the number of points is not prime, you can find segments with exactly the same number of points in them. What is your objective?