title: What is the *fastest* algorithm for detecting intersection between polyhedra?
body: <p>Say there are <em>n</em> 3-dimensional objects (polyhedra). Is the fastest way to calculate the intersection of all objects O(n ^ 2)?</p>
  
  <p>Right now, I'm using a library that essentially forces T(n) to equal n ^ 2:</p>
  
  <pre><code>for each object: // there are n objects
      get list of intersecting objects // this takes n steps
  </code></pre>
  
  <p>That literally takes n ^ 2 steps.</p>
  
  <p>The only <em>faster</em> way that I can think of is still O(n ^ 2), but T(n) = n(n+1) / 2, or (n*n + n) / 2.</p>
  
  <p>Here's pseudocode:</p>
  
  <pre><code>for(int i = 0; i &lt; len(objects) - 1; i++)
      for(int j = i + 1; j &lt; len(objects); j++)
          if object at i intersects object at j:
              object at i . addToIntersectList ( object at j )
              object at j . addToIntersectList ( object at i )
  </code></pre>
  
  <p>This way we don't have to check to see if two objects intersect twice. I know there are about 3000 objects in the list I am iterating through. This algorithm takes 4501500 steps, whereas the original algorithm takes nearly double that, 9000000 steps.</p>
  
  <p>Am I missing something? Is this the best we can get?</p>