# Exists a dedicated non-O(n²) Algorithm for avoiding to have overlapping elements?

I am generating positions in a random fashion.

In the game world, instantiated elements have a radius, and shouldn't overlap.

The problem is that they will overlap because I use a usual random number generator combined with other fanciness. I can't use other random number generation algorithms where I can guarantee that the elements will never overlap.

A way to solve this is to use a spatial data structure and search for the nearest neighbors in that tree. When I insert an element into that tree, I update it accordingly.

This solution would do the work and it would be fast but my question is:

Is there a dedicated algorithm without that Tree implementation complexity which is faster than O(n²)?

• This question makes very little sense. Why can't you use other RNG algorithms? Why can't you use the algorithm you know works and is fast? – Steven Stadnicki Jan 8 '14 at 5:15

A way to solve this is to use a spatial data structure and search for the nearest neighbors in that tree. When I insert an element into that tree, I update it accordingly.

You need a tree data structure to actually get a better worst case using scenario, this will give you an O(log N) for nearest neighbor searches.

Grids on the other hand will still give you a better average solution, so you only need to check the adjacent cells, but this will not be as good as the tree structure.

I can also think of spatial hashing but am not particularly sure that a nearest neighbor problem can be solved and give a better performance that trees since I didn't try it myself. You can also check this wikipedia page for the common nearest neighbor search algorithms.

Regarding your number generation I want to point out to this article, that says that using your RNG or grid sampling won't give you points that really look naturally random (will be either too messy or too regular) and why you should use a Poisson point disk sampling instead.

http://devmag.org.za/2009/05/03/poisson-disk-sampling/

• i know the solutions with the tree and i know jitered grid and poisson disc and variations. the question just was if there is an special algorithm to handle the neightbor problem without using a tree (as an add-hoc solution). Its actually a "is there a special algorithm for this special case" rather than "how can i realize it" – Quonux Jan 9 '14 at 21:58
• @Quonux check my edit. – concept3d Jan 9 '14 at 22:12
• the spartial hashing is actually a solution besides a complete tree, the time complexity for an access is theoretically O(1). A neightbor check is also simple to realize, thx, i hadn't think of that data-structure :) – Quonux Jan 9 '14 at 22:23
• "won't give you points that really look naturally random" actually I think the first image looks more natural (it looks like the night sky) although less uniformly distributed. I guess it depends on the use case which end result is more desirable. – jhocking Jan 20 '14 at 13:38
• @jhocking I think you are right. my wording wasn't particularly in-accurate, to be honest I couldn't find a better word. If you suggest a better wording I will edit it. – concept3d Jan 20 '14 at 13:47

option 1 divide your area up into a grid and assign each object to a cell according to there position, now you only have to check the cell it is in and the neighbouring cells (those only if the new object gets close enough)

option 2 sort the objects according to 1 axis and then you can easily find all objects that overlap a certain interval on that axis (this breaks down in dimensions higher than 2 though)

• Both of these are still O(n²) in the worst case, though considerably better on average than the naive approach. – MooseBoys Jan 8 '14 at 1:20