论文标题
几何组测试
Geometric group testing
论文作者
论文摘要
小组测试涉及在一组$ m $项目中识别$ t $有缺陷的项目，其中每个测试报告特定的项目是否包含至少一个缺陷。在非自适应组测试中，要测试的子集已提前固定。通过一次测试多个项目，所需数量的测试数量可以小得多。实际上，对于$ t \ in \ Mathcal {o}（1）$，已知（非自动）测试的最佳数字为$θ（\ log {m}）$。 在本文中，我们考虑了在几何环境中非自适应组测试的问题，其中这些项目是$ d $维欧几里得空间中的点，而测试是轴 - 平行的盒子（超矩形）。我们在此几何约束下所需的测试数量上呈现上限和下限。与一般组合案例相反，我们的几何环境中的界限是$ m $的多项式。例如，我们的结果暗示，在飞机中确定一对$ m $点的有缺陷对总是需要$ω（m^{3/5}）$测试，并且存在$ \ mathcal {o}（o {o}（m^{2/3}）$测试的$ m $点的配置，以便确定单个防御点的配置。测试始终是必要的，有时是足够的。
Group testing is concerned with identifying $t$ defective items in a set of $m$ items, where each test reports whether a specific subset of items contains at least one defective. In non-adaptive group testing, the subsets to be tested are fixed in advance. By testing multiple items at once, the required number of tests can be made much smaller than $m$. In fact, for $t \in \mathcal{O}(1)$, the optimal number of (non-adaptive) tests is known to be $Θ(\log{m})$. In this paper, we consider the problem of non-adaptive group testing in a geometric setting, where the items are points in $d$-dimensional Euclidean space and the tests are axis-parallel boxes (hyperrectangles). We present upper and lower bounds on the required number of tests under this geometric constraint. In contrast to the general, combinatorial case, the bounds in our geometric setting are polynomial in $m$. For instance, our results imply that identifying a defective pair in a set of $m$ points in the plane always requires $Ω(m^{3/5})$ tests, and there exist configurations of $m$ points for which $\mathcal{O}(m^{2/3})$ tests are sufficient, whereas to identify a single defective point in the plane, $Θ(m^{1/2})$ tests are always necessary and sometimes sufficient.
