{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T04:31:08Z","timestamp":1726201868827},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540133452"},{"type":"electronic","value":"9783540388869"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1984]]},"DOI":"10.1007\/3-540-13345-3_10","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:01:52Z","timestamp":1330192912000},"page":"119-127","source":"Crossref","is-referenced-by-count":11,"title":["The complexity and decidability of separation"],"prefix":"10.1007","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Ottmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eljas","family":"Soisalon-Soininen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Derick","family":"Wood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B. S. Baker","year":"1980","unstructured":"Baker, B.S., Coffman Jr., E.G., and Rivest, R.L., Orthogonal Packings in Two Dimensions, SIAM Journal on Computing 9 (1980), 846\u2013855.","journal-title":"SIAM Journal on Computing"},{"key":"10_CR2","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"C-29","author":"J. L. Bentley","year":"1980","unstructured":"Bentley, J.L., and Wood, D., An Optimal Worst-Case Algorithm for Reporting Intersections of Rectangles, IEEE Transactions on Computers, C-29 (1980), 571\u2013577.","journal-title":"IEEE Transactions on Computers"},{"key":"10_CR3","unstructured":"Edelsbrunner, H., A Time-and Space-Optimal Solution for the Planar All Intersecting Rectangles Problem. Tech. Rep., University of Graz, IIG Rep. 50, April 1980."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., and Yao, F.F., On Translating a Set of Rectangles, Proceedings of the Tenth Annual ACM-SIGACT Symposium on Theory of Computing (1980), 154\u2013160.","DOI":"10.1145\/800141.804663"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Joseph, D.A., and Whitesides, S.H., On the Movement of Robot Arms in 2-Dimensional Bounded Regions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, (1982), 280\u2013289.","DOI":"10.1109\/SFCS.1982.29"},{"key":"10_CR6","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T. Lozano-Perez","year":"1979","unstructured":"Lozano-Perez, T., and Wesley, M., An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles, Communications of the ACM 22 (1979), 560\u2013570.","journal-title":"Communications of the ACM"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"O'D\u00fanlaing, C., Sharir, M., and Yap, C.K., Retraction: A New Approach to Motion Planning, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (1983), 207\u2013220.","DOI":"10.1145\/800061.808750"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Reif, J., Complexity of the Mover's Problem and Generalizations, Proceeding of the 20th Annual Symposium on Foundations of Computer Science (1979), 421\u2013427.","DOI":"10.1109\/SFCS.1979.10"},{"key":"10_CR9","unstructured":"Schlag, M., Liao, Y.Z., and Wong, C.K., An Algorithm for Optimal Two-Dimensional Compaction Layouts, IBM Research Center, Yorktown, Research Report RC 9739, 1982."},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Schwartz, J.T., and Sharir, M., On the Piano Mover's Problem: I. The Special Case of a Rigid Polygonal Body Moving amidst Polygonal Barriers, Communications on Pure and Applied Mathematics (1983), to appear.","DOI":"10.1002\/cpa.3160360305"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Schwartz, J.T., and Sharir, M., On the Piano Mover's Problem: II. General Techniques for Computing Topological Properties of Real Alagebraic Manifolds, Advances in Applied Mathematics (1983), to appear.","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"10_CR12","unstructured":"Schwartz, J.T., and Sharir, M., On the Piano Mover's Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving amidst Polygonal Barriers, New York University Courant Institute Computer Science Technical Report, 1983."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-13345-3_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:52:44Z","timestamp":1619556764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-13345-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984]]},"ISBN":["9783540133452","9783540388869"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-13345-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1984]]}}}