Hello,
I was thinking on problem of 1D clustering. I have n points and i want to partition them in k sets minimizing the within-cluster sum of squares, like here: http://en.wikipedia.org/wiki/K-means_clustering#Description. I can solve this problem using dynamic programming in O(n^2 * k). Can i improve this time? Can i use divide and conquer optimization? If yes, how to proof it?
Thanks!
EDIT: Here's a paper that explains the standard dynamic programming O(n^2 * k): http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf
Think abouth convex hull trick optimization. Makes complexity to O(KNlogN)
Based on this: http://codeforces.me/blog/entry/8219 , isn't clear to me how to put the recorrence in the form of Convex Hull Optimization2. For me it fits better in Divide and Conquer Optimization, but i can't proof that it's correct and i don't know a fast way to calculate the cost function using Divide and Conquer Optimization.