{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:11:57Z","timestamp":1787501517745,"version":"build-2736575974"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete &amp; Computational Geometry"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf02570694","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T00:22:00Z","timestamp":1177719720000},"page":"9-29","source":"Crossref","is-referenced-by-count":4,"title":["Piecewise linear paths among convex obstacles"],"prefix":"10.1007","volume":"14","author":[{"given":"M.","family":"de Berg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Matou\u0161ek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"O.","family":"Schwarzkopf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1995,7,1]]},"reference":[{"key":"BF02570694_CR1","series-title":"Lecture Notes in Computer Science","first-page":"373","volume-title":"Proc. 1st Workshop on Algorithms and Data Structures (WADS)","author":"H. Alt","year":"1989","unstructured":"[AY] H. Alt and C. K. Yap. Motion planning incl-environments: a case for a realistic model.Proc. 1st Workshop on Algorithms and Data Structures (WADS), pp. 373\u2013380. Lecture Notes in Computer Science, vol. 382. Springer-Verlag, Berlin, 1989."},{"key":"BF02570694_CR2","doi-asserted-by":"crossref","unstructured":"[AS1] B. Aronov and M. Sharir. The union of convex polyhedra in three dimensions.Proc. 34th Annual IEEE Symp. on Foundations of Computer Science, pp. 519\u2013527, 1993.","DOI":"10.1109\/SFCS.1993.366835"},{"key":"BF02570694_CR3","unstructured":"[AS2] B. Aronov and M. Sharir. The common exterior of convex polygons in the plane. Manuscript, 1994."},{"key":"BF02570694_CR4","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02293035","volume":"8","author":"J.-D. Boissonnat","year":"1992","unstructured":"[BDS+] J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry.Discrete Comput. Geom., 8:51\u201371, 1992.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570694_CR5","series-title":"ACM-MIT Press Doctoral Dissertation Award Series","volume-title":"The Complexity of Robot Motion","author":"J. Canny","year":"1987","unstructured":"[C] J. Canny.The Complexity of Robot Motion. ACM-MIT Press Doctoral Dissertation Award Series. MIT Press, Cambridge, MA, 1987."},{"key":"BF02570694_CR6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF02187909","volume":"3","author":"J. Canny","year":"1988","unstructured":"[CD] J. Canny and B. R. Donald, Simplified Voronoi diagrams.Discrete Comput. Geom., 3:219\u2013236, 1988.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570694_CR7","unstructured":"[CEG+] B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink. Computing a face in an arrangement of line segments.Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, pp. 441\u2013448, 1991."},{"key":"BF02570694_CR8","doi-asserted-by":"crossref","unstructured":"[CLD] L. P. Chew and R. L. Drysdale, III. Voronoi diagrams based on convex distance functions.Proc. 1st Annual ACM Symp. on Computational Geometry, pp. 235\u2013244, 1985.","DOI":"10.1145\/323233.323264"},{"key":"BF02570694_CR9","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D. P. Dobkin","year":"1985","unstructured":"[DK] D. P. Dobkin and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra.J. Algorithms, 6:381\u2013392, 1985.","journal-title":"J. Algorithms"},{"key":"BF02570694_CR10","unstructured":"[KM] T. C. Kao and D. M. Mount. An algorithm for computing compacted Voronoi diagrams defined by convex distance functions.Proc. Third Canadian Conf. on Computational Geometry, pp. 104\u2013109, 1991."},{"key":"BF02570694_CR11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"[KLPS] 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:59\u201371, 1986.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570694_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot Motion Planning","author":"J.-C. Latombe","year":"1991","unstructured":"[L] J.-C. Latombe.Robot Motion Planning. Kluwer, Dordrecht, 1991."},{"key":"BF02570694_CR13","unstructured":"[MS] N. Miller and M. Sharir. Efficient randomized algorithm for constructing the union of fat triangles and of pseudodiscs. Unpublished manuscript."},{"key":"BF02570694_CR14","volume-title":"Elements of Algebraic Topology","author":"J. R. Munkers","year":"1984","unstructured":"[M] J. R. Munkers,Elements of Algebraic Topology. Addison-Wesley, Reading, MA, 1984."},{"key":"BF02570694_CR15","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4576-6","volume-title":"An Introduction to Algebraic Topology","author":"J. J. Rothman","year":"1988","unstructured":"[R] J. J. Rothman,An Introduction to Algebraic Topology. Graduate Texts in Mathematics, vol. 119. Springer-Verlag, New York, 1988."},{"key":"BF02570694_CR16","unstructured":"[S] S. Sifrony. A real nearly linear algorithm for translating a convex polygon. Technical Report 476, New York University, 1989."},{"key":"BF02570694_CR17","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/B978-0-444-88071-0.50013-8","volume-title":"Algorithms and Complexity","author":"J. T. Schwartz","year":"1990","unstructured":"[SS] J. T. Schwartz and M. Sharir. Algorithmic motion planning in robotics. In J. van Leeuwen, editor,Algorithms and Complexity, pp. 391\u2013430. Elsevier, Amsterdam, 1990."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570694.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02570694\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T11:59:43Z","timestamp":1558180783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02570694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF02570694"],"URL":"https:\/\/doi.org\/10.1007\/bf02570694","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}