{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T11:24:21Z","timestamp":1761391461728},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1988,6,1]],"date-time":"1988-06-01T00:00:00Z","timestamp":581126400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1988,6]]},"DOI":"10.1007\/bf01934088","type":"journal-article","created":{"date-parts":[[2005,7,30]],"date-time":"2005-07-30T20:16:11Z","timestamp":1122754571000},"page":"227-241","source":"Crossref","is-referenced-by-count":26,"title":["Scanline algorithms on a grid"],"prefix":"10.1007","volume":"28","author":[{"given":"Rolf G.","family":"Karlsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark H.","family":"Overmars","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"BF01934088_CR1","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"C-28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. Ottman,Algorithms for reporting and counting geometric intersections, IEEE Trans. Comp. C-28, 9 (1979), 643\u2013647.","journal-title":"IEEE Trans. Comp."},{"key":"BF01934088_CR2","doi-asserted-by":"crossref","unstructured":"B. Chazelle,Intersecting is easier than sorting, Proc. 16th Annual ACM Symposium on Theory of Computing (1984), 125\u2013234.","DOI":"10.1145\/800057.808674"},{"key":"BF01934088_CR3","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1080\/00207168308803365","volume":"13","author":"H. Edelsbrunner","year":"1983","unstructured":"H. Edelsbrunner,A new approach to rectangle intersections, Part II, Int. J. Comput. Math. 13 (1983), 221\u2013229.","journal-title":"Int. J. Comput. Math."},{"issue":"2","key":"BF01934088_CR4","first-page":"171","volume":"18","author":"H. Edelsbrunner","year":"1984","unstructured":"H. Edelsbrunner, J. van Leeuwen, T. Ottmann and D. Wood,Computing the connected components of simple rectilinear geometrical objects in d-space, R.A.I.R.O. Theoretical Informatics 18, 2 (1984), 171\u2013183.","journal-title":"R.A.I.R.O. Theoretical Informatics"},{"key":"BF01934088_CR5","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","volume":"2","author":"R. A. Jarvis","year":"1973","unstructured":"R. A. Jarvis,On the identification of the convex hull of a finite set of points in the plane, Information Processing Lett. 2 (1973), 18\u201321.","journal-title":"Information Processing Lett."},{"issue":"4","key":"BF01934088_CR6","first-page":"295","volume":"15","author":"D. B. Johnson","year":"1982","unstructured":"D. B. Johnson,A priority queue in which initialization and queue operations take O(loglogD)time, Math. Systems Theory 15, 4 (1982), 295\u2013310.","journal-title":"Math. Systems Theory"},{"key":"BF01934088_CR7","unstructured":"R. G. Karlsson,Algorithms in a restricted universe, Ph.D. thesis, University of Waterloo, 1984, Dept of Computer Science Tech. Report CS-84-50."},{"key":"BF01934088_CR8","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BFb0024008","volume":"182","author":"R. G. Karlsson","year":"1985","unstructured":"R. G. Karlsson and J. I. Munro,Proximity on a Grid, Proc. 2nd Symposium on Theoretical Aspects of Computer Science, Springer-Verlag Lecture Notes in Computer Science 182 (1985), 187\u2013196.","journal-title":"Springer-Verlag Lecture Notes in Computer Science"},{"key":"BF01934088_CR9","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0020-0190(88)90188-3","volume":"26","author":"R. G. Karlsson","year":"1988","unstructured":"R. G. Karlsson and M. H. Overmars,Normalized divide and conquer: A scaling technique for solving multi-dimensional problems, Information Processing Lett. 26 (1988), 307\u2013312.","journal-title":"Information Processing Lett."},{"key":"BF01934088_CR10","unstructured":"J. M. Keil and D. G. Kirkpatrick,Computational geometry on integer grids, Proc. 19th Annual Allerton Conference (1981), 41\u201350."},{"key":"BF01934088_CR11","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","volume":"28","author":"D. Kirkpatrick","year":"1984","unstructured":"D. Kirkpatrick and S. Reisch,Upper bounds for sorting integers on random access machines, Theoretical Computer Science 28 (1984), 263\u2013276.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"BF01934088_CR12","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H. T. Kung","year":"1975","unstructured":"H. T. Kung, F. Luccio and F. P. Preparata,On finding the maxima of a set of vectors, J. ACM 22, 4 (1975), 469\u2013476.","journal-title":"J. ACM"},{"key":"BF01934088_CR13","unstructured":"E. M. McCreight,Efficient algorithms for enumerating intersecting intervals and rectangles, Xerox Alto Res. Center, Report PARC CSL-80-9, 1980."},{"key":"BF01934088_CR14","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0214046","volume":"14","author":"F. W. Myers","year":"1985","unstructured":"F. W. Myers,An O(E logE +I)expected time algorithm for the planar segment intersection problem, SIAM J. Computing 14 (1985), 625\u2013637.","journal-title":"SIAM J. Computing"},{"key":"BF01934088_CR15","unstructured":"H. M\u00fcller,Rastered point location, Proc. Workshop on Graphtheoretic Concepts in Computer Science (WG85), Trauner Verlag, 1985, 281\u2013293."},{"key":"BF01934088_CR16","unstructured":"M. H. Overmars,Efficient data structures for range searching on a grid, to appear in J. of Algorithms."},{"key":"BF01934088_CR17","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry, An Introduction, Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"BF01934088_CR18","doi-asserted-by":"crossref","unstructured":"E. Soisalon-Soininen and D. Wood,An optimal algorithm for testing for safety and detecting deadlock in locked transaction systems, Proc. ACM Symposium on Principles of Data Bases (1982), 108\u2013116.","DOI":"10.1145\/588111.588130"},{"issue":"3","key":"BF01934088_CR19","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas,Preserving order in a forest in less than logarithmic time and linear space, Information Processing Lett. 6, 3 (1977), 80\u201382.","journal-title":"Information Processing Lett."},{"issue":"2","key":"BF01934088_CR20","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D. E. Willard","year":"1983","unstructured":"D. E. Willard,Log-logarithmic worst-case range queries are possible in Space \u0398(n), Information Processing Lett. 17, 2 (1983), 81\u201384.","journal-title":"Information Processing Lett."},{"key":"BF01934088_CR21","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0022-0000(84)90020-5","volume":"28","author":"D. E. Willard","year":"1984","unstructured":"D. E. Willard,New trie data structures which support very fast search operations, J. Comput. Syst. Sci. 28 (1984), 379\u2013394.","journal-title":"J. Comput. Syst. Sci."},{"key":"BF01934088_CR22","doi-asserted-by":"crossref","unstructured":"M. Z. Yannakakis, C. H. Papadimitriou and H. T. Kung,Locking policies: safety and freedom for deadlock, Proc. 20th Annual IEEE Symposium on Foundations of Computer Science (1979), 286\u2013297.","DOI":"10.1109\/SFCS.1979.22"}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01934088.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01934088\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01934088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T01:09:57Z","timestamp":1557450597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01934088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1988,6]]}},"alternative-id":["BF01934088"],"URL":"https:\/\/doi.org\/10.1007\/bf01934088","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,6]]}}}