Counting and representing intersections among triangles in three dimensions
Esther E. Ezra, Micha Sharir · 2004
We present an algorithm that efficiently counts all intersecting triples among a collection T of triangles in R3 in nearly-quadratic time. This solves a problem posed by Pellegrini, [18]. Using a variant of the technique, one can represent the set of all κ triple intersections, in compact form, as the disjoint union of complete tripartite hypergraphs, which requires nearly-quadratic construction time and storage. Our approach also applies to any collection of convex planar objects of constant description complexity in R3$, with the same performance bounds. We also prove that this counting problem belongs to the 3SUM-hard family, and thus our algorithm is likely to be nearly optimal (since it is believed that 3SUM-hard problems cannot be solved in subquadratic time).