Approximate Levels in Line Arrangements
Jiřı́ Matoušek · SIAM Journal on Computing · 1991
An arrangement L of n lines in the plane is considered. A d-approximate level k for L is a polygonal line meeting every vertical exactly once, such that for its every point p there are at least $k - d$ and at most $k + d$ lines of L above p. A d-approximate leveling for L is a collection $P_1 ,P_2 , \cdots ,P_{\lfloor n / 2d \rfloor }$, where every $P_i $ is a d-approximate level $2di$. A deterministic algorithm is given that, for a given L and a parameter $r \leqq n$, computes an $(n / r)$-approximate leveling for L, whose approximate levels consist of $O(r^2 )$ segments in total. The time complexity of this algorithm is $O(nr^{4 / 3} (\log n)^{4 / 3} (\log \log n + \log r)^c )$ (c a small constant), which is now outperformed by algorithms of Matoušek [Proc. 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 1–10] and Agarwal [Proc. 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 11#8211;21]. A substantially different and elementary method is used here. An approximate leveling can be directly used for approximate halfplanar range counting, but it can also be used for plane partitioning applications, and thus as a subroutine in many recent computational geometry algorithms.