Approximating the  \(\lambda \) -low-density Value

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 objects is \(\lambda \) -low-density. To select the most efficient algorithm for a certain input, one often needs to approximate the \(\lambda \) -low-density value, or density for short. In this paper, we show that given a set of n objects in \(\mathbb {R}^2\) , one can \((2+\varepsilon )\) -approximate the density value in \(O(n \log n + \lambda n/\varepsilon ^4)\) time. Finally, we argue that some real-world trajectory data sets have small density values, warranting the recent development of specialised algorithms. This is done by computing approximate density values for 12 real-world trajectory data sets.