In article <3f48adc3@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>>     My project is actually to make 3D renderings from GPS data, so I
>> necessarily will have a large set of datapoints..
>
>   I don't know anything about this type of algorithms, but I'm pretty
> sure there must be a much faster than O(n^4) algorithm for this.
> I would say that it's extremely rare that O(n^4) would be the fastest
> you can do something related to a set of points.
>   I very wild guess is that there exists sone O((n^2)*log n) or even O(n^2)
> algorithm. It would make sense.
>   OTOH, I think there are some matrix-handling algorithms which are O(n^3),
> so it's not impossible that that would be the faster possible for this
> problem as well.

Delaunay triangulation takes O(n log n) time if I recall correctly.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message