Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications
Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications
复制标题
3维排列中浅层的垂直分解及其应用
DOI：
10.1145/220279.220284
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
P. Agarwal;A. Efrat;M. Sharir
令$ {\ cal f} $为$ n $ bivariate代数函数的集合。我们表明，$ {\ le} k $ - 安排$ {\ cal a}的垂直分解的组合复杂性（{\ cal f}）$ is $ o（k^{3+ \ varepsilon} \ psi（{n/k}））$，对于任何$ \ varepsilon <0 $，其中$ \ psi（r）$是最大值$ {\ cal f} $的最多$ r $功能的子集的下部信封的复杂性。在最坏的情况下，这种结合几乎是最佳的，这意味着在双变量代数函数的排列中存在较小的浅插条。我们还提供了这些结果的许多应用，包括：（i）几个通用三维范围搜索问题的数据结构； （ii）在各种相当一般的距离功能下搜索最接近邻居的平面的动态数据结构； （iii）百分比的动态数据结构，用于在相当通用的距离函数下维持最接近的双重百分比，以及用于维持一组点的最小跨度树，以改进（近乎二次的）算法，以最小的两部分euclidean euclidean匹配飞机; （iv）在静态和动态设置中某些几何优化问题的有效算法。
Let ${\cal F}$ be a collection of $n$ bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the ${\le}k$-level of the arrangement ${\cal A}({\cal F})$ is $O(k^{3+\varepsilon}\psi({n/k}))$, for any $\varepsilon<0$, where $\psi (r)$ is the maximum complexity of the lower envelope of a subset of at most $r$ functions of ${\cal F}$. This bound is nearly optimal in the worst case, and implies the existence of shallow cuttings of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including: (i) data structures for several generalized three-dimensional range searching problems; (ii) dynamic data structures for planar nearest and farthest neighbor searching under various fairly general distance functions; (iii) %dynamic data structures for maintaining bichromatic %closest pairs under a fairly general distance function, and for %maintaining minimum spanning trees of a set of points under an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.