<p>Yes. You can do better than the trivial $O(n^2)$ time bound, but you are not going to enjoy it....</p>

<p>You can reduce the problem of deciding if there are intersecting pairs of triangles to $O(n)$ ray shooting queries among triangles, and using some heavy machinery (i.e., range searching techniques) you would get something. See Theorem 7.1 in the paper below. </p>

<p>You should also get something as far as detecting all $k$ intersecting pairs, but the bound is going to be useful only if $k$ is truly small (say, between $n$ and $n^{5/4}$).</p>

<p>In practice, some quadtree based heuristic should work reasonably well, but I am just speculating. </p>

<p><a href="https://www.cs.duke.edu/~pankaj/publications/papers/semi-range.pdf" rel="nofollow">https://www.cs.duke.edu/~pankaj/publications/papers/semi-range.pdf</a></p>

CC BY-SA 3.0
2014-11-25T13:48:07.397Z
Well, that is something at least!  Thank you very much for weighing in.  I kind of doubt anyone is going to beat this answer, so I will accept this for now.  Regarding practicality, in most CAD applications you could probably assume k ~ $O(n^{2/3})$, so this seems like it could perhaps be a speed up, though cuttings and partition trees are pretty hairy to implement. :/
Mikola
CC BY-SA 3.0
2014-11-25T07:51:04.057Z
2014-11-25T07:51:04.057Z
Sariel Har-Peled
<p>What is the fastest known algorithm to report all intersecting pairs amongst a collection of $n$ simplices, each with dimension at most $r \leq d$ embedded in $\mathbb{R}^d$ (for small $d$)?</p>

<p>In the case where $d=2$ and all simplices are line segments, this problem can be solved in $O((n+k) \log(n))$ time using the <a href="https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm" rel="nofollow">standard sweep line algorithm</a>, where $k$ is the number of intersections.</p>

<p>Are there generalizations of this technique to higher dimensions and with higher dimensional simplices (for example, find all intersections of a set of triangles in 3D)?</p>

<p>For clarification, I am most interested in the case where the dimension, $d$, is small, so it would be reasonable to assume that the cost of testing intersection between two simplices is $O(1)$.  Under this assumption, there is a trivial $O(n^2)$ algorithm (just test all pairs), but it would be nice to be able to do better.</p>

<p>The motivation for this would be to generalize sweep line intersection to 3D or higher dimensions.  This would be useful for computing overlay operations (especially CSG) in 3D, or snap-rounding.  Conventional approaches to this problem rely on spatial partitioning trees, though the performance and analysis of these techniques is somewhat sketchy (ie purely empirical, and not always great in the worst case even in practice).  It would be nice to know a solution to this problem which is supported by rigorous analysis.</p>

CC BY-SA 3.0
2014-11-24T00:33:03.843Z
What do you mean by _detect the intersections_?  If you want to decide whether the intersection is empty or not, it can be done by linear programming.  If you want to enumerate all vertices of the intersection, that is the convex hull problem (conversion between the H-representation and the V-representation of a convex polytope).
Tsuyoshi Ito
CC BY-SA 3.0
2014-11-24T00:37:52.063Z
I know that between any pair of simplices you can test intersection with linear programming.  Assume for this problem that this test is unit cost.  I want to report all pairs of simplices which intersect in as little time as possible.  The naive algorithm here would be $O(n^2)$, but can you do better?
Mikola
CC BY-SA 3.0
2014-11-24T13:49:50.713Z
In what sense can this problem be solved in O(n log n) time when d=2?  In the worst case, you have to output Ω(n^2) pairs.
Tsuyoshi Ito
CC BY-SA 3.0
2014-11-24T14:46:41.320Z
Right, the algorithm is output sensitive, $O(n \log(n) + k)$.  Forgot to add the extra factor, edited to clarify.
Mikola
<cg.comp-geom>
Algorithm to find all intersections in set of simplices
Mikola
# Algorithm to find all intersections in set of simplices

(Asked by: username_0 on 2014-11-23)

What is the fastest known algorithm to report all intersecting pairs amongst a collection of $n$ simplices, each with dimension at most $r \leq d$ embedded in $\mathbb{R}^d$ (for small $d$)?

In the case where $d=2$ and all simplices are line segments, this problem can be solved in $O((n+k) \log(n))$ time using the [standard sweep line algorithm](https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm), where $k$ is the number of intersections.

Are there generalizations of this technique to higher dimensions and with higher dimensional simplices (for example, find all intersections of a set of triangles in 3D)?

For clarification, I am most interested in the case where the dimension, $d$, is small, so it would be reasonable to assume that the cost of testing intersection between two simplices is $O(1)$. Under this assumption, there is a trivial $O(n^2)$ algorithm (just test all pairs), but it would be nice to be able to do better.

The motivation for this would be to generalize sweep line intersection to 3D or higher dimensions. This would be useful for computing overlay operations (especially CSG) in 3D, or snap-rounding. Conventional approaches to this problem rely on spatial partitioning trees, though the performance and analysis of these techniques is somewhat sketchy (ie purely empirical, and not always great in the worst case even in practice). It would be nice to know a solution to this problem which is supported by rigorous analysis.

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: What do you mean by _detect the intersections_?  If you want to decide whether the intersection is empty or not, it can be done by linear programming.  If you want to enumerate all vertices of the intersection, that is the convex hull problem (conversion between the H-representation and the V-representation of a convex polytope).  
> **username_0**: I know that between any pair of simplices you can test intersection with linear programming.  Assume for this problem that this test is unit cost.  I want to report all pairs of simplices which intersect in as little time as possible.  The naive algorithm here would be $O(n^2)$, but can you do better?  
> **username_1**: In what sense can this problem be solved in O(n log n) time when d=2?  In the worst case, you have to output Ω(n^2) pairs.  
> **username_0**: Right, the algorithm is output sensitive, $O(n \log(n) + k)$.  Forgot to add the extra factor, edited to clarify.  

---

## 1 answers

### Answer by username_2 on 2014-11-25. Score: 4 | Accepted answer

Yes. You can do better than the trivial $O(n^2)$ time bound, but you are not going to enjoy it....

You can reduce the problem of deciding if there are intersecting pairs of triangles to $O(n)$ ray shooting queries among triangles, and using some heavy machinery (i.e., range searching techniques) you would get something. See Theorem 7.1 in the paper below.

You should also get something as far as detecting all $k$ intersecting pairs, but the bound is going to be useful only if $k$ is truly small (say, between $n$ and $n^{5/4}$).

In practice, some quadtree based heuristic should work reasonably well, but I am just speculating.

<https://www.cs.duke.edu/~pankaj/publications/papers/semi-range.pdf>

> **Comments:**
> **username_0**: Well, that is something at least!  Thank you very much for weighing in.  I kind of doubt anyone is going to beat this answer, so I will accept this for now.  Regarding practicality, in most CAD applications you could probably assume k ~ $O(n^{2/3})$, so this seems like it could perhaps be a speed up, though cuttings and partition trees are pretty hairy to implement. :/  

---

