[This is my first post to CrossValidated, I hope I'm not off-topic]
I have data consisting of ~10^6 points in 3D space. We want to try out some surface fitting algorithms that cannot handle this high number of points. So I would like to to use some means of data reductions (maybe ~1:100 needed) - clustering seems appropriate to me here. The data contains a lot of almost identical points.
Does anyone know a reasonable simple algorithms with an available implementation? Implementation in python, octave or matlab is preferred. I could roll my own, but I think this should have been solved before.