{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:39:04Z","timestamp":1756993144821},"reference-count":23,"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":["Discrete Comput Geom"],"published-print":{"date-parts":[[1988,6]]},"DOI":"10.1007\/bf02187902","type":"journal-article","created":{"date-parts":[[2005,10,29]],"date-time":"2005-10-29T08:11:50Z","timestamp":1130573510000},"page":"123-136","source":"Crossref","is-referenced-by-count":56,"title":["Separating two simple polygons by a sequence of translations"],"prefix":"10.1007","volume":"3","author":[{"given":"R.","family":"Pollack","sequence":"first","affiliation":[]},{"given":"M.","family":"Sharir","sequence":"additional","affiliation":[]},{"given":"S.","family":"Sifrony","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1988,6,1]]},"reference":[{"key":"BF02187902_CR1","unstructured":"B. K. Bhattacharya and G. T. Toussaint, A Linear Algorithm for Determining Translation Separability of Two Simple Polygons, Technical Report SOCS-86.1, McGill University, 1986."},{"key":"BF02187902_CR2","doi-asserted-by":"crossref","unstructured":"B. Chazelle, A theorem on polygon cutting with applications,Proceedings of the 23th IEEE Symposium on Foundations of Computer Science, 339\u2013349, 1982.","DOI":"10.1109\/SFCS.1982.58"},{"key":"BF02187902_CR3","unstructured":"B. Chazelle, The polygon containment problem, inAdvances in Computing Research, Vol. I (F. P. Preparata, ed.), 1\u201332, JAI Press, 1983."},{"key":"BF02187902_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Proceedings of the ACM Symposium on Computational Geometry, 135\u2013146, 1985.","DOI":"10.1145\/323233.323252"},{"key":"BF02187902_CR5","doi-asserted-by":"crossref","unstructured":"L. P. Chew and R. L. Drysdale, III, Voronoi diagrams based on convex distance functions,Proceedings of the ACM Symposium on Computational Geometry, 235\u2013244, 1985.","DOI":"10.1145\/323233.323264"},{"key":"BF02187902_CR6","unstructured":"H. Edelsbrunner and E. Welzl, Private communication, 1985."},{"key":"BF02187902_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BFb0015744","volume-title":"A fast algorithm for polygon containment by translation","author":"S. Fortune","year":"1985","unstructured":"S. Fortune, A fast algorithm for polygon containment by translation,Proceedings of the 12th International Colloquium on Automata, Languages and Programming, 189\u2013198, Lecture Notes in Computer Science, Vol. 194, Springer-Verlag, New York, 1985."},{"key":"BF02187902_CR8","doi-asserted-by":"crossref","unstructured":"L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear time algorithms for shortest path and visibility problems inside simple polygons.Proceedings of the second ACM Symposium on Computational Geometry, 1\u201313, 1986.","DOI":"10.1145\/10515.10516"},{"key":"BF02187902_CR9","doi-asserted-by":"crossref","unstructured":"L. Guibas, L. Ramshaw, and J. Stolfi, A kinetic framework for computational geometry,Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, 100\u2013111, 1983.","DOI":"10.1109\/SFCS.1983.1"},{"key":"BF02187902_CR10","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica 6 (1986), 151\u2013177.","journal-title":"Combinatorica"},{"key":"BF02187902_CR11","doi-asserted-by":"crossref","unstructured":"K. Kedem, and M. Sharir, An efficient algorithm for planning translational collision-free motion of a convex polygonal object in 2-dimensional space admidst polygonal obstacles,Proceedings of the ACM Symposium on Computational Geometry, 75\u201380, 1985.","DOI":"10.1145\/323233.323244"},{"key":"BF02187902_CR12","unstructured":"K. Kedem and M. Sharir, An Efficient Motion Planning Algoritm for a Convex Rigid Polygonal Object in 2-Dimensional Polygonal Space, Technical Report 253, Computer Science Department, Courant Institute, October 1986."},{"key":"BF02187902_CR13","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,Discrete Comput. Geom. 1 (1986), 59\u201372.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187902_CR14","doi-asserted-by":"crossref","unstructured":"D. Leven and M. Sharir, An efficient and simple motion-planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,Proceedings of the ACM Symposium on Computational Geometry, 221\u2013227, 1985 (also to appear inJ. Algorithms).","DOI":"10.1145\/323233.323262"},{"key":"BF02187902_CR15","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02187867","volume":"2","author":"D. Leven","year":"1987","unstructured":"D. Leven and M. Sharir, Planning a purely translational motion of a convex object in two-dimensional space using generalized Voronoi diagrams,Discrete Comput. Geom. 2 (1987), 9\u201331.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187902_CR16","doi-asserted-by":"crossref","unstructured":"D. Leven and M. Sharir, On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space,Discrete Comput. Geom., to appear.","DOI":"10.1007\/BF02187883"},{"key":"BF02187902_CR17","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T. Lozano Perez","year":"1979","unstructured":"T. Lozano Perez and M. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles,Comm. ACM 22 (1979), 560\u2013570.","journal-title":"Comm. ACM"},{"key":"BF02187902_CR18","unstructured":"J. R. Sack and G. Toussaint, Separability of pairs of polygons through single translations, manuscript."},{"key":"BF02187902_CR19","doi-asserted-by":"crossref","unstructured":"S. Sifrony and M. Sharir, A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space,Algorithmica, to appear.","DOI":"10.1007\/BF01840368"},{"key":"BF02187902_CR20","unstructured":"S. Suri, Finding minimum-link paths inside a simple polygon,Comput. Vision, Graphics Image Process., to appear."},{"key":"BF02187902_CR21","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan and C. Van Wyk, AnO(n log logn) time algorithm for triangulating simple polygons, manuscript, August 1986.","DOI":"10.1145\/12130.12170"},{"key":"BF02187902_CR22","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/B978-0-444-87806-9.50018-9","volume-title":"Computational Geometry","author":"G. T. Toussaint","year":"1985","unstructured":"G. T. Toussaint, Movable separability of sets, inComputational Geometry (G. T. Toussaint, ed.), 335\u2013375, North-Holland, Amsterdam, 1985."},{"key":"BF02187902_CR23","unstructured":"C. K. Yap, How to Move a Chair Through a Door, Technical Report 238, Computer Science Department, Courant Institute, August 1986."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187902.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187902\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T15:20:17Z","timestamp":1586532017000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1988,6]]}},"alternative-id":["BF02187902"],"URL":"https:\/\/doi.org\/10.1007\/bf02187902","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,6]]}}}