论文标题
在四个维度的四面体中搜索的交叉点搜索
Intersection Searching amid Tetrahedra in Four Dimensions
论文作者
论文摘要
我们在四个维度，涉及段，三角形和四面体的四个维度上开发了相交查询的数据结构。具体而言，我们研究了三个主要问题：（i）预处理一组$ n $ tetrahedra in $ \ reals^4 $ in数据结构中，以在给定的四面体中回答段交流查询（称为\ emph {sent emph {sagment emph {sengment omph {sagment trahedron section coolies}）。 （ii）预处理一组$ n $三角形在$ \ reals^4 $中添加到一个数据结构中，该数据结构支持输入三角形的三角交流查询（称为\ emph {triangle-triangle-triangle交点交点查询}）。 （iii）在输入段中支持四面体交流查询的数据结构中的一组$ n $ sem段，该数据结构支持四面体交流查询（称为\ emph {tetrahedron-sement-section-section section crotse coolies}）。在每个问题中，我们都希望检测一个交叉点，或计算或报告所有交叉点。据我们所知，这些问题以前尚未得到研究。 对于问题（i），我们首先提出了一个“标准”解决方案，对于任何预先指定的值$ n \ le s \ le n^6 $的所谓存储参数$ s $，产生具有$ o^*（s）$存储和预期预处理的数据结构，并在$ o^*（n/s^*what of tirs（what of tirs）中回答一个交叉点（以下是什么） $ o^*（\ cdot）$符号隐藏了多项式因素）。对于使用类似参数的问题（ii）和（iii），我们提出了一种具有相同渐近性能界限的解决方案。然后，我们改进了问题（i）的解决方案，并提供了一个更复杂的数据结构，该数据结构使用$ o^*（n^{2}）$存储和预期的预处理，并回答$ o^*（n^{1/2}）中的分段四面体交点查询。
We develop data structures for intersection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study three main problems: (i) Preprocess a set of $n$ tetrahedra in $\reals^4$ into a data structure for answering segment-intersection queries amid the given tetrahedra (referred to as \emph{segment-tetrahedron intersection queries}). (ii) Preprocess a set of $n$ triangles in $\reals^4$ into a data structure that supports triangle-intersection queries amid the input triangles (referred to as \emph{triangle-triangle intersection queries}). (iii) Preprocess a set of $n$ segments in $\reals^4$ into a data structure that supports tetrahedron-intersection queries amid the input segments (referred to as \emph{tetrahedron-segment intersection queries}). In each problem we want either to detect an intersection, or to count or report all intersections. 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 \le s \le n^6$ of a so-called 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^*(\cdot)$ notation hides subpolynomial factors). For problems (ii) and (iii), 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^{2})$ storage and expected preprocessing, and answers a segment-tetrahedron intersection query in $O^*(n^{1/2})$ time.
