Improved Bounds for the Union of Locally Fat Objects in the Plane
Improved Bounds for the Union of Locally Fat Objects in the Plane
复制标题
改进了平面中局部胖对象联合的界限
DOI：
10.1137/120891241
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
B. Aronov;M. D. Berg;Esther Ezra;M. Sharir
我们证明，对于任何$\gamma > 0$，平面中具有恒定复杂度的$n$局部$\gamma$胖对象的联合的组合复杂度为$\frac{n}{\gamma^4} 2^{O（\log^*n）}$。对于$\gamma$-胖三角形的特殊情况，上界提高到$O（n \log^*{n} + \frac{n}{\gamma}\log^2{\frac{1}{\gamma}}）$。
We show that, for any $\gamma > 0$, the combinatorial complexity of the union of $n$ locally $\gamma$-fat objects of constant complexity in the plane is $\frac{n}{\gamma^4} 2^{O(\log^*n)}$. For the special case of $\gamma$-fat triangles, the bound improves to $O(n \log^*{n} + \frac{n}{\gamma}\log^2{\frac{1}{\gamma}})$.