CODEWITHSUNDEEP
c++algorithmperformancesorting
Nick de Boer
Nick de Boer

Reputation: 73

Is a KD tree still one of the best algorithms to use on moving objects

Say you have a list of objects and every object needs to calculate his closest object to shoot. This object has a x and a y value. Also the objects are moving. Will a kd tree still be usefull? I am not sure because if the objects are moving you have to keep creating this kd tree.

What algorithm can i use for the best speed (Preferably with Big O)

Upvotes: 5

Views: 1293

Answers (1)

m.raynal
m.raynal

Reputation: 3113

The k-d tree is a very, very efficient data structure to determine closest neighbors in a euclidian space with cooordinates.
It would take a really huge number of objects to have issues with a k-d tree generation (it is generated in O(n log²n), so almost linear time, and search of all nearest neighbors takes O(n log n), very cheap too). So you would probably have issues with the rest of the program as well.

From the look of your question, it seems that all you need to keep track of is the closest neighbor of a number of points in a euclidian space. I'd suggest you to start with a vanilla implementation of a k-d tree, and, in the extreme and unlikely case where the generation of the k-d tree would be too costy in terms of time, or of memory, to try and find a way to keep track of several neighbors for each element, and update the list only when needed.
But honestly, I've been working with k-d tree in the past, and I remember that despite the data set being quite big (dozens of millions of points in a 2D space), the generation and search were fast enough to seem negligible w.r.t the other operations.

Upvotes: 5

Related Questions