论文标题
深度查询和最大深度的基于偶性的近似算法
Duality-based approximation algorithms for depth queries and maximum depth
论文作者
论文摘要
我们设计了一个有效的数据结构，用于计算安排中任何查询点的适当定义的近似深度，$ \ MATHCAL {a}（s）$的$ n $ n $ half $ n $ halfplanes或三角形的$ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ n $ n $ n $ n $ n $ n。然后，我们使用此结构在$ \ Mathcal {a}（s）$中找到一个近似最大深度的点。具体来说，给定一个错误参数$ε> 0 $，我们计算，对于任何查询点$ q $，$ q $的深度的低估$ d^ - （q）$，仅计数包含$ q $的对象，但当$ q $是$ q $是$ε$ - $ε$ - $ε$ - $ε$ - 将对象排除在其边界上。同样，我们计算了一个高估的$ d^+（q）$，该$计数包含$ q $的所有对象，但也可能计算不包含$ q $但$ q $的对象，而$ q $是$ε$ - close在其边界上。我们的半平面和半空间的算法在输入对象的数量和查询数中是线性的，并且其运行时间对$ε$的依赖性比早期技术要好得多。对于三角形和更高的维度，我们的改进尤其重要。
We design an efficient data structure for computing a suitably defined approximate depth of any query point in the arrangement $\mathcal{A}(S)$ of a collection $S$ of $n$ halfplanes or triangles in the plane or of halfspaces or simplices in higher dimensions. We then use this structure to find a point of an approximate maximum depth in $\mathcal{A}(S)$. Specifically, given an error parameter $ε>0$, we compute, for any query point $q$, an underestimate $d^-(q)$ of the depth of $q$, that counts only objects containing $q$, but is allowed to exclude objects when $q$ is $ε$-close to their boundary. Similarly, we compute an overestimate $d^+(q)$ that counts all objects containing $q$ but may also count objects that do not contain $q$ but $q$ is $ε$-close to their boundary. Our algorithms for halfplanes and halfspaces are linear in the number of input objects and in the number of queries, and the dependence of their running time on $ε$ is considerably better than that of earlier techniques. Our improvements are particularly substantial for triangles and in higher dimensions.
