Name
Abstract | ||
|---|---|---|
We present an algorithm that efficiently counts all intersecting triples among a collection T of triangles in ℝ3 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 ℝ3$, 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). |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.comgeo.2005.02.003 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
three dimensions | Conference | 32 |
Issue | ISSN | ISBN |
3 | Computational Geometry: Theory and Applications | 1-58113-885-7 |
Citations | PageRank | References |
10 | 0.53 | 24 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Esther Ezra | 1 | 148 | 18.36 |
| Micha Sharir | 2 | 8405 | 1183.84 |