{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:20:44Z","timestamp":1762100444388},"publisher-location":"Berlin\/Heidelberg","reference-count":26,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540528261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032047","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"400-413","source":"Crossref","is-referenced-by-count":77,"title":["Determining the separation of preprocessed polyhedra \u2014 A unified approach"],"prefix":"10.1007","author":[{"given":"David P.","family":"Dobkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David G.","family":"Kirkpatrick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Avis,D., ElGindy, H. and Seidel, R., A simple online algorithm for convex polyhedra, in Computational Geometry, G. Toussaint, ed., Springer Verlag, 1985, 23\u201342.","DOI":"10.1016\/B978-0-444-87806-9.50007-4"},{"key":"31_CR2","unstructured":"Chan, F. and Wang, C., Optimal algorithms for the intersection and the minimum distance problems between planar polygons, Technical Report TR-82-8, Department of Computer Science, University of Alberta, August, 1982."},{"key":"31_CR3","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1109\/SFCS.1989.63539","volume":"30","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., An optimal algorithm for intersecting three-dimensional convex polyhedra, IEEE Sympos. on Found. of Comp. Sci. 30 (1989), 586\u2013591.","journal-title":"IEEE Sympos. on Found. of Comp. Sci."},{"key":"31_CR4","first-page":"146","volume":"12","author":"B. Chazelle","year":"1980","unstructured":"Chazelle, B. and Dobkin, D. Detection is easier than computation, ACM Sympos. on Theory of Comput. 12 (1980), 146\u2013153.","journal-title":"ACM Sympos. on Theory of Comput."},{"key":"31_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/7531.24036","volume":"34","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B. and Dobkin, D. Intersection of convex objects in two and three dimensions, JACM 34 (1987), 1\u201327.","journal-title":"JACM"},{"key":"31_CR6","first-page":"153","volume":"39","author":"N. Dadoun","year":"1989","unstructured":"Dadoun, N. and Kirkpatrick, D., Parallel construction of subdivision hierarchies, JCSS 39 (1989), 153\u2013165.","journal-title":"JCSS"},{"key":"31_CR7","unstructured":"Dadoun, N. and Kirkpatrick, D., Cooperative subdivisions algorithms with applications, Allerton Conference, 1989, to appear."},{"key":"31_CR8","first-page":"55","volume":"1","author":"N. Dadoun","year":"1985","unstructured":"Dadoun, N., Kirkpatrick, D. and Walsh, J. The geometry of beam tracing, ACM Sympos. on Comp. Geom. 1 (1985), 55\u201361.","journal-title":"ACM Sympos. on Comp. Geom."},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/BFb0012765","volume":"140","author":"D. Dobkin","year":"1982","unstructured":"Dobkin, D. and Kirkpatrick, D., Fast detection of polyhedral intersections, Lecture Notes in Computer Science 140 (1982) 154\u2013165.","journal-title":"Lecture Notes in Computer Science"},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0304-3975(82)90120-7","volume":"27","author":"D. Dobkin","year":"1983","unstructured":"Dobkin, D. and Kirkpatrick, D., Fast detection of polyhedral intersection, TCS 27 (1983), 241\u2013253.","journal-title":"TCS"},{"key":"31_CR11","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D. Dobkin","year":"1985","unstructured":"Dobkin, D. and Kirkpatrick, D., A linear algorithm for determining the separation of convex polyhedra, J. Algorithms 6 (1985) 381\u2013392.","journal-title":"J. Algorithms"},{"key":"31_CR12","unstructured":"Dobkin, D. and Sonvaine, D., Detecting the intersection of convex objects in the plane, Princeton University Technical Report CS-TR-231-89, October, 1989."},{"key":"31_CR13","unstructured":"Dobkin, D. and Souvaine, D., Detecting the intersection of convex objects in 3 dimensions, in preparation."},{"key":"31_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H., Algorithms in Combinatorial Geometry, Springer Verlag, Berlin, 1987."},{"key":"31_CR15","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0196-6774(85)90039-2","volume":"6","author":"H. Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H., Computing the extreme distance between two convex polygons, J. Algorithms 6 (1985), 213\u2013224.","journal-title":"J. Algorithms"},{"key":"31_CR16","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(85)90107-3","volume":"21","author":"H. Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H. and Maurer, H., Finding extreme points in three dimensions and solving the post-office problem in the plane, IPL 21 (1985), 39\u201347.","journal-title":"IPL"},{"key":"31_CR17","volume-title":"Convex Polytopes","author":"B. Grunbaum","year":"1987","unstructured":"Grunbaum, B., Convex Polytopes, John Wiley&Sons, London, 1987."},{"key":"31_CR18","first-page":"100","volume":"24","author":"L. Guibas","year":"1983","unstructured":"Guibas, L., Ramshaw, L., and Stolfi, J., A kinetic framework for computational geometry, IEEE Sympos. Found. Comp. Sci. 24 (1983), 100\u2013111.","journal-title":"IEEE Sympos. Found. Comp. Sci."},{"key":"31_CR19","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D., Optimal search in planar subdivisions, SIAM J. Comput. 12 (1983), 28\u201335.","journal-title":"SIAM J. Comput."},{"key":"31_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69900-9","volume-title":"Data Structures and Algorithms 3: Computational Geometry","author":"K. Mehlhourn","year":"1984","unstructured":"Mehlhourn, K., Data Structures and Algorithms 3: Computational Geometry Springer Verlag, Berlin, 1984."},{"key":"31_CR21","unstructured":"Mehlhourn, K. and Simon, K., Intersecting two polyhedra one of which is convex, Univ. Saarland Technical report, Saarbrucken, West Germany, 1986."},{"key":"31_CR22","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(78)90051-8","volume":"7","author":"D. Mueller","year":"1978","unstructured":"Mueller, D. and Preparata, F., Finding the intersection of two convex polyhedra, TCS 7 (1978) 217\u2013236.","journal-title":"TCS"},{"key":"31_CR23","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F. Preparata","year":"1977","unstructured":"Preparata, F. and Hong, S., Convex hulls of finites sets of points in two and three dimensions, CACM 20 (1977), 87\u201393.","journal-title":"CACM"},{"key":"31_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry \u2014 an Introduction","author":"F. Preparata","year":"1985","unstructured":"Preparata, F. and Shamos, M., Computational Geometry \u2014 an Introduction Springer Verlag, New York, NY, 1985."},{"key":"31_CR25","unstructured":"Souvaine, D., Computational geometry in a curved world, Ph.D. dissertation, Princeton University, 1986."},{"key":"31_CR26","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(81)90051-X","volume":"13","author":"J. Schwartz","year":"1981","unstructured":"Schwartz, J., Finding the minimum distance between two convex polygons, IPL 13 (1981), 168\u2013170.","journal-title":"IPL"}],"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\/BFb0032047.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:05:34Z","timestamp":1607551534000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0032047","relation":{},"subject":[]}}