论文标题
近似lambda-low密度值
Approximating the lambda-low-density value
论文作者
论文摘要
现实的输入模型的使用在理论社区中广受欢迎。假设一个现实的输入模型通常会排除复杂的假设输入，并且分析产生的界限可以更好地反映算法在实践中的行为。 多边形曲线和线段最受欢迎的模型之一是$λ$ - 低密度。要选择特定输入的最有效算法，通常需要计算$λ$ - 低密度的值，或者至少一个近似值。在本文中，我们表明在$ \ mathbb {r}^2 $中给定一组$ n $行段，一个人可以计算$ 3 $ - approximation的$λ$ -LOW密度为$ O（n \ log log n + log n +λn）$时间。我们还展示了如何维持$λ$ - 低密度值的$ 3 $ - 附件，同时允许在$ o（\ log n +λ^2）中插入新的细分市场，$每个更新$摊销时间。 最后，我们认为许多现实世界中的数据集具有小的$λ$ - 低密度值，这需要最新的专用算法的开发。这是通过计算$ 12 $现实世界数据集的大约$λ$ - 低密度值来完成的。
The use of realistic input models has gained popularity in the theory community. Assuming a realistic input model often precludes complicated hypothetical inputs, and the analysis yields bounds that better reflect the behaviour of algorithms in practice. One of the most popular models for polygonal curves and line segments is $λ$-low-density. To select the most efficient algorithm for a certain input, one often needs to compute the $λ$-low-density value, or at least an approximate value. In this paper, we show that given a set of $n$ line segments in $\mathbb{R}^2$ one can compute a $3$-approximation of the $λ$-low density value in $O(n \log n + λn)$ time. We also show how to maintain a $3$-approximation of the $λ$-low density value while allowing insertions of new segments in $O(\log n + λ^2)$ amortized time per update. Finally, we argue that many real-world data sets have a small $λ$-low density value, warranting the recent development of specialised algorithms. This is done by computing approximate $λ$-low density values for $12$ real-world data sets.
