Approximating the lambda-low-density value

التفاصيل البيبلوغرافية
العنوان: Approximating the lambda-low-density value
المؤلفون: Gudmundsson, Joachim, Huang, Zijin, Wong, Sampson
سنة النشر: 2022
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Computational Geometry
الوصف: 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 $\lambda$-low-density. To select the most efficient algorithm for a certain input, one often needs to compute the $\lambda$-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 $\lambda$-low density value in $O(n \log n + \lambda n)$ time. We also show how to maintain a $3$-approximation of the $\lambda$-low density value while allowing insertions of new segments in $O(\log n + \lambda^2)$ amortized time per update. Finally, we argue that many real-world data sets have a small $\lambda$-low density value, warranting the recent development of specialised algorithms. This is done by computing approximate $\lambda$-low density values for $12$ real-world data sets.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2211.07039
رقم الأكسشن: edsarx.2211.07039
قاعدة البيانات: arXiv