{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:27:45Z","timestamp":1742401665541},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108566"},{"type":"electronic","value":"9783540387695"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10856-4_70","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:32:08Z","timestamp":1330191128000},"page":"1-15","source":"Crossref","is-referenced-by-count":8,"title":["The complexity of manipulating hierarchically defined sets of rectangles"],"prefix":"10.1007","author":[{"given":"Jon Louis","family":"Bentley","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Ottmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"1_CR1","unstructured":"Bentley, J.L. [1977]: Solution to Klee's rectangle problems, unpublished manuscript, Dept. of Computer Science, Carnegie-Mellon University, 1977."},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1109\/TC.1980.1675628","volume":"C-29","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L. and Wood, D. [1980]: An optimal worst-case algorithm for reporting intersections of rectangles, IEEE Transactions on Computers, Vol. C-29, 1980, 572\u2013577.","journal-title":"IEEE Transactions on Computers"},{"key":"1_CR3","unstructured":"Bentley, J.L., Haken, D., and Hon, R. [1980]: Statistics on VLSI Designs, Dept. of Computer Science, Carnegie-Mellon University, Technical Report CMU-CS-80."},{"key":"1_CR4","series-title":"Computer Science Technical Report","volume-title":"Connected Components of Orthogonal Geometric Objects","author":"H. Edelsbrunner","year":"1980","unstructured":"Edelsbrunner, H., van Leeuwen, J., Ottmann Th., and Wood, D. [1980]: Connected Components of Orthogonal Geometric Objects, Computer Science Technical Report, 1981, McMaster University, Hamilton, Ontario, Canada."},{"key":"1_CR5","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and Johnson, D.S. [1979]: Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"1_CR6","unstructured":"Haken, D. [1980]: A geometric design rule checker, VLSI Document V053, Carnegie-Mellon University, 9 June 80."},{"key":"1_CR7","unstructured":"Hon, R. [1980]: The Hierarchical Analysis of VLSI Designs, Thesis proposal, Carnegie-Mellon University, Dec. 1980."},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1080\/00029890.1977.11994404","volume":"84","author":"V. Klee","year":"1977","unstructured":"Klee, V. [1977]: Can the Measure of U[ai,bi] be computed in less than O(n log n) steps, Research Probl. Sect., Amer. Math. Monthly 84, 1977, 284\u2013285.","journal-title":"Amer. Math. Monthly"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Lauther [1980]: A Data Structure for Gridless Routing, 17th Design Automation Conference, Minneapolis 1980, 1\u20137.","DOI":"10.1145\/800139.804593"},{"key":"1_CR10","unstructured":"van Leeuwen, J. and Wood, D. [1979]: The Measure Problem for Rectangular Ranges in d-Space, Technical Report, RUU-CS-79-6, July 1979."},{"key":"1_CR11","unstructured":"McCreight, E. M. [1980]: Efficient Algorithms for Enumerating Intersecting Intervals and Rectangles. XEROX Palo Alto Research Center, 1980, Report CSL-80-9."},{"key":"1_CR12","unstructured":"Mead, C. and Conway, L. [1980]: Introduction to VLSI Systems, Addison-Wesley."},{"key":"1_CR13","series-title":"Technical Report","volume-title":"Planesweep algorithms for intersecting geometric figures","author":"J. Nievergelt","year":"1980","unstructured":"Nievergelt, J. and Preparata, F.P. [1980]: Planesweep algorithms for intersecting geometric figures, Technical Report (in preparation), Institut f\u00fcr Informatik, ETH Z\u00fcrich."},{"key":"1_CR14","unstructured":"Ottmann, Th. and Widmayer, P. [1981]: Reasonable encodings make Rectangle Problems Hard, Forschungsbericht des Instituts f\u00fcr Angewandte Informatik und Formale Beschreibungsverfahren, Universit\u00e4t Karlsruhe, 1981."},{"key":"1_CR15","series-title":"Computer Science Technical Report","volume-title":"Rectilinear line segment intersection, layered segment trees and dynamization","author":"V. Vaishnavi","year":"1980","unstructured":"Vaishnavi, V. and Wood, D. [1980]:Rectilinear line segment intersection, layered segment trees and dynamization, Computer Science Technical Report, 80-CS-8, McMaster University, Hamilton, Ontario, Canada."},{"key":"1_CR16","series-title":"Computer Science Technical Report","volume-title":"Computing the Perimeter of a Set of Rectangles","author":"P.M.B. Vitanyi","year":"1979","unstructured":"Vitanyi, P.M.B. and Wood, D. [1979]: Computing the Perimeter of a Set of Rectangles, Computer Science Technical Report, 79-CS-23, McMaster University, Hamilton, Ontario, Canada."},{"key":"1_CR17","unstructured":"Whitney, T. [1980]: Description of the Hierarchical Design Rule Filter, Caltech SSP File 4027, Oct. 1980."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1981"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10856-4_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:04:02Z","timestamp":1605643442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10856-4_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108566","9783540387695"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-10856-4_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}