# Are collision detection always O(n^2)?

Are physics engine able to decrease that complexity, for example by grouping objects who are near each other and check for collisions inside this group instead of against all objects ? (for example, far objects can be removed from a group by looking at its velocity and distance from other objects).

If not, does that make collision trivial for spheres (in 3d) or disk (in 2d) ? Should I make a double loop, or create an array of pairs instead ?

EDIT: For physics engine like bullet and box2d, is collision detection still O(N^2) ?

• Two words: Spatial partitioning – MichaelHouse Jun 15 '13 at 13:22
• – MichaelHouse Jun 15 '13 at 13:29
• You bet. I believe both have implementations of SAP (Sweep and Prune) (among others) which is a O(n log(n)) algorithm. Search for "Broad Phase Collision Detection" to learn more. – MichaelHouse Jun 15 '13 at 14:34
• @Byte56 Sweep and Prune has complexity O(n log(n)) only if you need to sort every time you test. You want to keep a sorted list of objects and each time you add one, just sort it to the correct place O(log(n)) therefore you get O(log(n) + n) = O(n). It gets very complicated when objects start moving though! – MartinTeeVarga Jun 15 '13 at 15:11
• @sm4, if the movements is limited then a few passes of bubble sort can take care of that (just mark the moved objects and move them forward or backward in the array until they are sorted. just watch out for other move objects – ratchet freak Jun 15 '13 at 22:58

Spatial division is always O(N^2) in worst case and that is what complexity in informatics is about.

However there are algorithms that work in linear time O(N). All of them are based on some kind of sweep line.

Basically you need to have your objects sorted by one coordinate. Let's say X. If you perform the sort every time before collision detection, the complexity will be O(N*logN). The trick is to sort only when you are adding objects to the scene and later when something in the scene changes. Sorting after movement is not trivial. See the linked paper below for an algorithm that takes into movement and still works in linear time.

Then you sweep from left to right. Each time your sweep line crosses beginning of an object, you put it inside a temporary list. Every time your sweep line exits the object, you take it out from the list. You consider collisions only inside this temporary list.

The naive sweep line is O(N^2) in worst case as well (you make all objects span the whole map from left to right), but you can make it O(N) by making it smarter (see link below). A really good algorithm will be quite complex.

This is simple diagram how the sweep line works:

The line sweeps from left to right. Objects are sorted by X coordinate.

• Case one: First two objects are checked. Nothing else matters.
• Case two: First object was checked and is gone from the list. Two and three are checked.
• Case three: Even if that object IS colliding, we don't check.
• Case four: Because we check in this case!

Algorithms like this have complexity O(C*N) = O(N).

Source: Two years of computational geometry courses.

In collision detection this is typically called Sweep and Prune, but sweep line family of algortithms is useful in many other fields.

Further recommended reading that I believe is out of scope of this question, but nevertheless interesting: Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal - This paper presents an enhanced Sweep and Prune algorithm that uses axis-aligned bounding boxes (AABB) with sorting that takes into account movement. Algorigthm presented in the paper works in linear time.

Now note that this is the best algorithm in theory. It doesn't mean that it is used. In practice, O(N^2) algorithm with spatial division will have better performance speed wise in typical case (close to O(N)) and some extra requirement for memory. This is because the constant C in O(C*N) can be very high! Since we usually have enough memory and typical cases have objects spread evenly in space - such algorithm will perform BETTER. But O(N) is the answer to the original question.

• does box2d/bullet use this ? – jokoon Jun 15 '13 at 14:35
• "Sweep and prune" is what this is normally called for physics. Nice thing is that you can keep the sorting updated as the simulation is advanced. Also, the sweep line in your graphic is a little off in terms of implementation (good for theory though) - you would just iterate over the box starts/ends, so you'd only be checking the actual potential collisions. Seen this method used to generate more capable spatial partitioning trees rather than used directly, too. – Sean Middleditch Jun 15 '13 at 15:50
• Since technically there can actually be O(N^2) pairwise collisions, it's not entirely true to say that sweep-and-prune is always O(N). Rather, the core complexity of the algorithm is O(N+c), where c is the number of collisions found by the algorithm - it's output-sensitive, much as many convex hull algorithms are. (Reference: en.wikipedia.org/wiki/Output-sensitive_algorithm ) – Steven Stadnicki Jun 15 '13 at 18:21
• You should back your claims with some publications or at least algorithm names. – sam hocevar Jun 16 '13 at 9:32
• @SamHocevar I've added a link to a really advanced Sweep and Prune algorithm that works in linear time with detailed breakdown of the constants. The fact that the algorithms are called "Sweep and Prune" was new to me, since I never worked with it. I have used these algorithms in map selection (which is kind of a collision of 1 point with other objects), so I just applied the knowledge. – MartinTeeVarga Jun 16 '13 at 9:52

No. Collision detection is not always O(N^2).

For instance, say we have a 100x100 space with objects with size 10x10. We could divide this space in cells of 10x10 with a grid.

Each object can be in up to 4 grid cells (it could fit right in a block or be "between" cells). We could keep a list of objects in each cell.

We only need to check for collisions in those cells. If there is a maximum number of objects per grid cell (say, there are never more than 4 objects in the same block), then collision detection for each object is O(1) and collision detection for all objects is O(N).

This is not the only way to avoid O(N^2) complexity. There are other methods, more adequate for other use-cases - often using tree-based data structures.

The algorithm I described is one type of Space partitioning, but there are other space partitioning algorithms. See Types of space partitioning data structures for some more algorithms that avoid the O(N^2) temporal complexity.

Both Box2D and Bullet support mechanisms to reduce the number of checked pairs.

From the manual, section 4.15:

Collision processing in a physics step can be divided into narrow-phase and broad-phase. In the narrow-phase we compute contact points between pairs of shapes. Imagine we have N shapes. Using brute force, we would need to perform the narrow-phase for N*N/2 pairs.

The b2BroadPhase class reduces this load by using a dynamic tree for pair management. This greatly reduces the number of narrow-phase calls.

Normally you do not interact with the broad-phase directly. Instead, Box2D creates and manages a broad-phase internally. Also, b2BroadPhase is designed with Box2D’s simulation loop in mind, so it is likely not suited for other use cases.

From the Bullet Wiki:

There are various kinds of broadphase algorithms that improve upon the naive O(n^2) algorithm that just returns the complete list of pairs. These optimised broadphases sometimes introduce even more non-colliding pairs but this is offset by their generally improved execution time. They have different performance characteristics and none outperform the others in all situations.

Dynamic AABB Tree

This is implemented by the btDbvtBroadphase in Bullet.

As the name suggests, this is a dynamic AABB tree. One useful feature of this broadphase is that the structure adapts dynamically to the dimensions of the world and its contents. It is very well optimized and a very good general purpose broadphase. It handles dynamic worlds where many objects are in motion, and object addition and removal is faster than SAP.

Sweep and Prune (SAP)

In Bullet, this is the AxisSweep range of classes. This is also a good general purpose broadphase, with a limitation that it requires a fixed world size, known in advance. This broadphase has the best performance for typical dynamics worlds, where most objects have little or no motion. Both btAxisSweep3 and bt32AxisSweep3 quantize the begin and end points for each axis as integers instead of floating point numbers, to improve performance.

The following link is a general introduction to broadphase and also a description of the Sweep and Prune algorithm (although it calls it "Sort and Sweep"):

http://en.wikipedia.org/wiki/Sweep_and_prune

• Some links to similar questions and outside resources would make this a great answer. – MichaelHouse Jun 15 '13 at 13:47
• This is wrong. You are still getting O(N^2). It will be much faster, something like N^2 / 100, but still N^2. As a proof, just consider that all objects happen to be in one cell. – MartinTeeVarga Jun 15 '13 at 14:15
• @sm4 This is worst-case O(N^2), which is indeed what happens if all objects are in one cell. However, in a physics engines, objects will typically not be in one cell. In my example, no object can ever share the same cell with more than 3 other objects. This would be what happens in a physics engine for "normal" objects (and by "normal" I mean "not just a sensor"). – luiscubal Jun 15 '13 at 14:20
• I think your algorithm would require to check in the 8 cells around, not just the 4 cells. – jokoon Jun 15 '13 at 14:27
• @luiscubal Complexity is always "worst case". In theory you are looking for "guaranteed" complexity. It's the same with quicksort, which is O(N^2) and mergesort, which is O(N*logN). Quicksort performs better on real data and has lower spatial requirement. But mergesort has guaranteed better complexity. If you need to proof something, use mergesort. If you need to sort something, use quicksort. – MartinTeeVarga Jun 15 '13 at 14:59

O(N^2) refers to the fact that if you have N objects, figuring out what is colliding with what is, worst case, N^2 collision computations. Say you have 3 objects. To find "who is hitting who", you have to find:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?


That's 6 checks for collisions, or N*(N-1) checks. In asymptotic analysis we'd expand the polynomial and approximate as O(N^2). If you had 100 objects, then that'd be 100*99, which is close enough to 100*100.

So if you partition space using an octree for example, the average number of comparisons between bodies is reduced. If it is possible for all the objects to gather into a very small area (say if you're doing some kind of particle flow simulation, where particles can gather in the same area) then the O(N^2) may still occur at points in the simulation (at which points you'll see slowdown).

So, the whole point of O(N^2) there is because of the nature of each body checking every other body in the scene. That's just the nature of the computation. A lot of things can help to make this cheaper though. Even a scene graph (say detecting between objects in the same room only) will reduce the number of collision computations to be done significantly, but it will still be O(M^2) (where M is the number of objects in the room to be collision detected against). Spherical bounding volumes make the initial check very fast (if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS), so even if collision detection is O(N^2), the bounding sphere computations are likely to happen very fast.

• There's no need to take brute force checking as a reference: regardless of clever algorithms, N objects can each collide with all other objects, giving O(N^2) collisions that require O(N^2) work to be processed. Good algorithms can only do better when there are less collisions. – Lorenzo Gatti Jul 31 '15 at 16:21