4
$\begingroup$

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, 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 24, 2014 at 0:33
  • 1
    $\begingroup$ 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? $\endgroup$
    – Mikola
    Commented Nov 24, 2014 at 0:37
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 24, 2014 at 13:49
  • $\begingroup$ Right, the algorithm is output sensitive, $O(n \log(n) + k)$. Forgot to add the extra factor, edited to clarify. $\endgroup$
    – Mikola
    Commented Nov 24, 2014 at 14:46

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. :/ $\endgroup$
    – Mikola
    Commented Nov 25, 2014 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.