Counting and representing intersections among triangles in three dimensions

AbstractWe 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 [M. Pellegrini, On counting pairs of intersecting segments and off-line triangle range searching, Algorithmica 17 (1997) 380–398]. 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 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 in the worst case