{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:31:01Z","timestamp":1787340661334,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1991,4]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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\u0161ek [Proc. 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 1\u201310] 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.<\/jats:p>","DOI":"10.1137\/0220013","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:34:57Z","timestamp":1109226897000},"page":"222-227","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Levels in Line Arrangements"],"prefix":"10.1137","volume":"20","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal,  A deterministic algorithm for partitioning arrangements of lines and its applications,  Proc. 5th Annual ACM Symposium on Computational Geometry, Saarbr\u00fccken, FRG,  1989,  11\u201321","DOI":"10.1145\/73833.73835"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal,  Ray shooting and other applications of spanning trees with low stabbing number,  Proc. 5th Annual ACM Symposium on Computational Geometry, Saarbr\u00fccken, FRG,  1989,  315\u2013325","DOI":"10.1145\/73833.73868"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-1001852-0"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187742"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90088-8"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0215019"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,  Construction of  $\\varepsilon$-nets,  Proc. 5th Annual ACM Symposium on Computational Geometry, Saarbr\u00fccken, FRG,  1989,  1\u201310","DOI":"10.1145\/73833.73834"},{"key":"R13","volume-title":"Approximate halfplanar range counting","author":"Matou\u0161ek J.","year":"1987"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Emo Welzl,  Partition trees for triangle counting and other range searching problems,  Proceedings of the Fourth Annual Symposium on Computational Geometry (Urbana, IL, 1988), ACM, New York,  1988,  23\u201333 1 213 461","DOI":"10.1145\/73393.73397"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187686"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0220013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:14Z","timestamp":1787337794000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0220013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["10.1137\/0220013"],"URL":"https:\/\/doi.org\/10.1137\/0220013","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,4]]}}}