Abstract
We develop data structures for intersection detection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study two main problems: (i) Preprocess a set of n tetrahedra in {ℝ}⁴ into a data structure for answering segmentintersection queries amid the given tetrahedra (referred to as segmenttetrahedron intersection queries), and (ii) Preprocess a set of n triangles in {ℝ}⁴ into a data structure that supports triangleintersection queries amid the input triangles (referred to as triangletriangle intersection queries). As far as we can tell, these problems have not been previously studied.
For problem (i), we first present a "standard" solution which, for any prespecified value n ≤ s ≤ n⁶ of a socalled storage parameter s, yields a data structure with O^*(s) storage and expected preprocessing, which answers an intersection query in O^*(n/s^{1/6}) time (here and in what follows, the O^*(⋅) notation hides subpolynomial factors). For problem (ii), using similar arguments, we present a solution that has the same asymptotic performance bounds.
We then improve the solution for problem (i), and present a more intricate data structure that uses O^*(n²) storage and expected preprocessing, and answers a segmenttetrahedron intersection query in O^*(n^{1/2}) time. Using the parametric search technique of Agarwal and Matoušek [P. K. Agarwal and J. Matoušek, 1993], we can obtain data structures with similar performance bounds for the rayshooting problem amid tetrahedra in {ℝ}⁴. Unfortunately, so far we do not know how to obtain a similar improvement for problem (ii).
Our algorithms are based on a primaldual technique for range searching with semialgebraic sets, based on recent advances in this area [P. K. Agarwal et al., 2021; J. Matoušek and Z. Patáková, 2015]. As this is a result of independent interest, we spell out the details of this technique.
As an application, we present a solution to the problem of "continuous collision detection" amid moving tetrahedra in 3space. That is, the workspace consists of n tetrahedra, each moving at its own fixed velocity, and the goal is to detect a collision between some pair of moving tetrahedra. Using our solutions to problems (i) and (ii), we obtain an algorithm that detects a collision in O^*(n^{12/7}) expected time. We also present further applications, including an outputsensitive algorithm for constructing the arrangement of n tetrahedra in ℝ⁴ and an outputsensitive algorithm for constructing the intersection or union of two or several nonconvex polyhedra in ℝ⁴.
BibTeX  Entry
@InProceedings{ezra_et_al:LIPIcs.ESA.2022.51,
author = {Ezra, Esther and Sharir, Micha},
title = {{Intersection Searching Amid Tetrahedra in 4Space and Efficient Continuous Collision Detection}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {51:151:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16989},
URN = {urn:nbn:de:0030drops169895},
doi = {10.4230/LIPIcs.ESA.2022.51},
annote = {Keywords: Computational geometry, Ray shooting, Tetrahedra in \{\mathbb{R}\}⁴, Intersection queries in \{\mathbb{R}\}⁴, Polynomial partitioning, Range searching, Semialgebraic sets, Tradeoff}
}
Keywords: 

Computational geometry, Ray shooting, Tetrahedra in {ℝ}⁴, Intersection queries in {ℝ}⁴, Polynomial partitioning, Range searching, Semialgebraic sets, Tradeoff 
Collection: 

30th Annual European Symposium on Algorithms (ESA 2022) 
Issue Date: 

2022 
Date of publication: 

01.09.2022 