1991/04/01 by Jiřı́ Matoušek · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques #Digital Image Processing Techniques #Computational geometry #Mathematics #Combinatorics #Subroutine #Line (geometry) #Range (aeronautics) #Plane (geometry) #Geometry #Binary logarithm #Algorithm #Line segment #Discrete mathematics #Computer science
paper · doi:10.1137/0220013
openalex publication_date 1991/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
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 P1 ,P2 , ⋯ ,P\lfloor n / 2d \rfloor , where every Pi 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(r2 ) segments in total. The time complexity of this algorithm is O(nr4 / 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.