{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:08:01Z","timestamp":1761620881225,"version":"3.32.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1993,6,1]],"date-time":"1993-06-01T00:00:00Z","timestamp":738892800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,6]]},"DOI":"10.1007\/bf01190153","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T22:43:07Z","timestamp":1108680187000},"page":"518-533","source":"Crossref","is-referenced-by-count":111,"title":["Computing the intersection-depth of polyhedra"],"prefix":"10.1007","volume":"9","author":[{"given":"David","family":"Dobkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Kirkpatrick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"P. Agarwal. Ray shooting and other applications of spanning trees with low stabbing number.Proc. 5th ACM Symposium on Computational Geometry, pp. 315?325, 1989.","DOI":"10.1145\/73833.73868"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, L. Guibas, J. Saxe, and P. Shor. A linear time algorithm for computing the Voronoi diagram of a convex polygon.Discrete and Computational Geometry, 4:591?604, 1989.","journal-title":"Discrete and Computational Geometry"},{"key":"CR3","first-page":"557","volume":"E-68","author":"T. Asano","year":"1985","unstructured":"T. Asano. An efficient algorithm for finding the visibility polygons for a polygonal region with holes.Transactions of IECE of Japan, E-68:557?559, 1985.","journal-title":"Transactions of IECE of Japan"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"B. S. Baker, S. F. Fortune, and S. R. Mahaney. Polygon containment under translation.Journal of Algorithms, 532?548, 1986.","DOI":"10.1016\/0196-6774(86)90017-9"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J. Bentley","year":"1979","unstructured":"J. Bentley and T. A. Ottman. Algorithms for reporting and counting geometric intersections.IEEE Transactions on Computers, 28:643?647, 1979.","journal-title":"IEEE Transactions on Computers"},{"key":"CR6","unstructured":"C. E. Buckley and L. J. Leifer. A proximity metric for continuum path planning.Proc. 9th International Joint Conference on Artificial Intelligence, pp. 1096?1102, 1985."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"S. A. Cameron and R. K. Culley. Determining the minimum translation distance between two convex polyhedra.Proc. IEEE International Conference on Robotics and Automation, pp. 591?596, 1986.","DOI":"10.1109\/ROBOT.1986.1087645"},{"key":"CR8","unstructured":"B. Chazelle. Efficient polygon triangulation.Proc. IEEE Symposium on Foundations of Computer Science, pp. 220?230, 1990."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/7531.24036","volume":"34","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle and D. Dobkin. Intersection of convex objects in two and three dimensions.Journal of the Association for Computing Machinery, 34:1?27, 1987.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1109\/TC.1983.1676186","volume":"32","author":"F. Chin","year":"1983","unstructured":"F. Chin and C. A. Wang. Optimal algorithms for the intersection and the minimum distance problems between planar polygons.IEEE Transactions on Computers, 32:1203?1207, 1983.","journal-title":"IEEE Transactions on Computers"},{"key":"CR11","series-title":"Lecture Notes in Computer Science, Vol. 140","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/BFb0012765","volume-title":"Proc. ICALP '82","author":"D. Dobkin","year":"1982","unstructured":"D. Dobkin and D. Kirkpatrick. Fast detection of polyhedral intersections.Proc. ICALP '82, pp. 154?165. Lecture Notes in Computer Science, Vol. 140. Springer-Verlag, Berlin, 1982."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D. Dobkin","year":"1985","unstructured":"D. Dobkin and D. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra.Journal of Algorithms, 6:381?392, 1985.","journal-title":"Journal of Algorithms"},{"key":"CR13","series-title":"Lecture Notes in Computer Science, Vol. 443","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/BFb0032047","volume-title":"Proc. ICALP '90","author":"D. Dobkin","year":"1990","unstructured":"D. Dobkin and D. Kirkpatrick. Determining the separation of preprocessed polyhedra?a unified approach.Proc. ICALP '90, pp. 400?413. Lecture Notes in Computer Science, Vol. 443. Springer-Verlag, Berlin, 1990."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0196-6774(85)90039-2","volume":"6","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner. Computing the extreme distances between two convex polygons.Journal of Algorithms, 6:213?224, 1985.","journal-title":"Journal of Algorithms"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision.SIAM Journal on Computing, 15:317?340, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"H. El Gindy","year":"1981","unstructured":"H. El Gindy and D. Avis. A linear algorithm for computing the visibility polygon from a point.Journal of Algorithms, 2:186?197, 1981.","journal-title":"Journal of Algorithms"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M. Garey","year":"1978","unstructured":"M. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a simple polygon.Information Processing Letters, 7:175?179, 1978.","journal-title":"Information Processing Letters"},{"key":"CR18","volume-title":"Convex Polytopes","author":"B. Gr\u00fcnbaum","year":"1967","unstructured":"B. Gr\u00fcnbaum.Convex Polytopes. Wiley, New York, 1967."},{"key":"CR19","first-page":"64","volume-title":"Lecture Notes in Computer Science, Vol. 318","author":"L. Guibas","year":"1988","unstructured":"L. Guibas, M. Overmars, and M. Sharir. Intersecting line segments, ray shooting, and other applications of geometric partitioning techniques. InProc. First Scandinavian Workshop on Algorithm Theory, pp. 64?73. Lecture Notes in Computer Science, Vol. 318. Springer-Verlag, Berlin, 1988."},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"L. Guibas, L. Ramshaw, and J. Stolfi. A kinetic framework for computational geometry.Proc. 24th Foundations of Computer Science, pp. 100?111, Nov. 1983.","DOI":"10.1109\/SFCS.1983.1"},{"key":"CR21","first-page":"111","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"L. J. Guibas","year":"1989","unstructured":"L. J. Guibas and J. Stolfi. Ruler, compass, and computer: The design and analysis of geometric algorithms. Research Report 37, DEC Systems Research Center, 1989. Also appeared inTheoretical Foundations of Computer Graphics and CAD, pp. 111?165, Springer-Verlag, New York."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0196-6774(88)90003-X","volume":"9","author":"J. Hershberger","year":"1988","unstructured":"J. Hershberger and L. Guibas. AnO(n2) shortest path algorithm for a nonrotating convex body.Journal of Algorithms, 9:18?46, 1988.","journal-title":"Journal of Algorithms"},{"key":"CR23","first-page":"207","volume-title":"Lecture Notes in Computer Science, Vol. 158","author":"S. Hertel","year":"1983","unstructured":"S. Hertel and K. Mehlhorn.Fast Triangulation of Simple Polygons, pp. 207?218. Lecture Notes in Computer Science, Vol. 158. Springer-Verlag, Berlin, 1983."},{"key":"CR24","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 and Computational Geometry, 1:59?71, 1986.","journal-title":"Discrete and Computational Geometry"},{"key":"CR25","volume-title":"Technical Report","author":"S. S. Keerthi","year":"1989","unstructured":"S. S. Keerthi and K. Sridharan. Efficient algorithms for computing two measures of depth of collision between convex polygons. Technical Report, Department of Computer Science and Automation, IIS, Banglore, 1989."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"D. Kirkpatrick. Optimal search in planar subdivisions.SIAM Journal on Computing, 12:28?35, 1983.","journal-title":"SIAM Journal on Computing"},{"key":"CR27","volume-title":"EATCS Monographs on Theoretical Computer Science","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn.Multi-dimensional Searching and Computational Geometry. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1984."},{"key":"CR28","volume-title":"Report No. 112","author":"T. A. Ottman","year":"1982","unstructured":"T. A. Ottman, P. Widmeyer, and D. Wood. A fast algorithm for Boolean mask operations. Report No. 112, Instit\u00fct f\u00fcr Angewandte Mathematik und Formale Beschreibungsverfahren, W-7500 Karlsruhe, 1982."},{"key":"CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos.Computational Geometry: An Introduction. Springer-Verlag, New York, 1985."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"S. Suri and J. O'Rourke. Worst-case optimal algorithms for constructing visibility polygons with holes.Proc. 2nd ACM Symposium on Computational Geometry, pp. 14?23, 1986.","DOI":"10.1145\/10515.10517"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190153.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01190153\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T11:43:46Z","timestamp":1734954226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01190153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["BF01190153"],"URL":"https:\/\/doi.org\/10.1007\/bf01190153","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}