{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:36:34Z","timestamp":1725456994921},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540528261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032067","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"689-702","source":"Crossref","is-referenced-by-count":3,"title":["An input-size\/output-size trade-off in the time-complexity of rectilinear hidden surface removal"],"prefix":"10.1007","author":[{"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail J.","family":"Atallah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark H.","family":"Overmars","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"51_CR1","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"C-29","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley and D. Wood, \u201cAn Optimal Worst Case Algorithm for Reporting Intersections of Rectangles,\u201d IEEE Trans. on Computers, Vol. C-29, 1980, 571\u2013577.","journal-title":"IEEE Trans. on Computers"},{"key":"51_CR2","doi-asserted-by":"crossref","unstructured":"M. Bern, \u201cHidden Surface Removal for Rectangles,\u201d Proc. 4th ACM Symp. on Computational Geometry, 1988, 183\u2013192.","DOI":"10.1145\/73393.73412"},{"key":"51_CR3","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle, \u201cFiltering Search: A New Approach to Query-Answering,\u201d SIAM J. Comput., Vol. 15, 1986, 703\u2013724.","journal-title":"SIAM J. Comput."},{"key":"51_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle, \u201cIntersecting is Easier Than Sorting,\u201d 16th ACM Symp. on Theory of Comp., 1984, pp. 125\u2013134.","DOI":"10.1145\/800057.808674"},{"key":"51_CR5","unstructured":"J.I. Doh, \u201cVisibility Problems for Orthogonal Objects in Two-or Three-Dimensions,\u201d to appear in The Visual Computer."},{"key":"51_CR6","unstructured":"M.T. Goodrich, \u201cA Polygonal Approach to Hidden-Line Elimination,\u201d Proc. of 25th Annual Allerton Conference on Comm., Control, and Computing, 1987, 849\u2013858."},{"key":"51_CR7","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/S0734-189X(87)80114-7","volume":"40","author":"R.H. G\u00fcting","year":"1987","unstructured":"R.H. G\u00fcting and T. Ottmann, \u201cNew Algorithms For Special Cases of the Hidden Line Elimination Problem,\u201d Computer Vision, Graphics, and Image Processing, Vol. 40, 1987, 188\u2013204.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"51_CR8","unstructured":"L. Larmore, \u201cAn Optimal Query-Update Structure for the Interval Valuation Problem,\u201d manuscript, 1989."},{"key":"51_CR9","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/27625.27627","volume":"6","author":"M. McKenna","year":"1987","unstructured":"M. McKenna, \u201cWorst-case Optimal Hidden-Surface Removal,\u201d ACM Transactions on Graphics, Vol. 6, 1987, 19\u201328.","journal-title":"ACM Transactions on Graphics"},{"key":"51_CR10","unstructured":"K. Mehlhorn, private communication, October 1989."},{"key":"51_CR11","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1007\/BF01935366","volume":"25","author":"O. Nurmi","year":"1985","unstructured":"O. Nurmi, \u201cA Fast Line-Sweep Algorithm For Hidden Line Elimination,\u201d BIT, Vol. 25, 1985, 466\u2013472.","journal-title":"BIT"},{"key":"51_CR12","unstructured":"M. Paterson, private communication, October 1989."},{"key":"51_CR13","unstructured":"F.P. Preparata, J.S. Vitter, and M. Yvinec, \u201cComputation of the Axial View of a Set of Isothetic Parallelepipeds,\u201d Laboratoire d'Informatique de L'Ecole Normal Sup\u00e9rieure, D\u00e9partment de Math\u00e9matiques et d'Informatique, Report LIENS-88-1, 1988."},{"key":"51_CR14","unstructured":"A. Schmitt, \u201cOn the Time and Space Complexity of Certain Exact Hidden Line Algorithms,\u201d Universit\u00e4t Karlsruhe, Fakult\u00e4t f\u00fcr Informatik, Report 24\/81, 1981."},{"key":"51_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/356625.356626","volume":"6","author":"I.E. Sutherland","year":"1974","unstructured":"I.E. Sutherland, R.F. Sproull, and R.A. Schumacker, \u201cA Characterization of Ten Hidden-Surface Algorithms,\u201d Computing Surveys, Vol. 6, 1974, 1\u201325.","journal-title":"Computing Surveys"},{"key":"51_CR16","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, \u201cPresevering Order in a Forest in Less than Logarithmic Time and Linear Space,\u201d Information Processing Letters, Vol. 6, 1977, 80\u201382.","journal-title":"Information Processing Letters"},{"key":"51_CR17","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas, and E. Zijlstra, \u201cDesign and Implementation of an Efficient Priority Queue,\u201d Math. Systems Theory, Vol. 10, 1977, 99\u2013127.","journal-title":"Math. Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0032067.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:05:37Z","timestamp":1607551537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0032067","relation":{},"subject":[]}}