{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:40:27Z","timestamp":1734957627759,"version":"3.32.0"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1995,5,1]],"date-time":"1995-05-01T00:00:00Z","timestamp":799286400000},"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":[[1995,5]]},"DOI":"10.1007\/bf01190849","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T11:21:25Z","timestamp":1108725685000},"page":"462-471","source":"Crossref","is-referenced-by-count":4,"title":["Asymptotic speed-ups in constructive solid geometry"],"prefix":"10.1007","volume":"13","author":[{"given":"D.","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"B. Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra.Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 38?48.","DOI":"10.1109\/SFCS.1989.63539"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane.J. Assoc. Comput. Mech.,39 (1992), 1?54.","journal-title":"J. Assoc. Comput. Mech."},{"key":"CR3","unstructured":"R. F. Cohen and R. Tamassia. Dynamic expression trees and their applications.Proceedings of the 2nd ACM\/SIAM Symposium on Discrete Algorithms, 1991, pp. 52?61."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/378456.378472","volume":"22","author":"D. Dobkin","year":"1988","unstructured":"D. Dobkin, L. Guibas, J. Hershberger, and J. Snoeyink. An efficient algorithm for finding the CSG representation of a simple polygon.Comput. Graphics,22 (1988), 31?40.","journal-title":"Comput. Graphics"},{"key":"CR5","series-title":"LNCS, Vol. 140","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/BFb0012765","volume-title":"Proceedings of the 9th International Colloquium on Automata, Languages, and Programming","author":"D. P. Dobkin","year":"1982","unstructured":"D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection.Proceedings of the 9th International Colloquium on Automata, Languages, and Programming, 1982, pp. 154?165. LNCS, Vol. 140. Springer-Verlag, Berlin."},{"key":"CR6","volume-title":"EATCS Monographs on Theoretical Science","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Science. Springer-Verlag, Berlin, 1987."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement.J. Comput. System Sci.,38 (1989), 165?194.","journal-title":"J. Comput. System Sci."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"G. N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity andk smallest spanning trees.Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 632?641.","DOI":"10.1109\/SFCS.1991.185429"},{"key":"CR9","unstructured":"M. T. Goodrich. Applying parallel processing techniques to classification problems in constrictive solid geometry.Proceedings of the 1st ACM\/SIAM Symposium on Discrete Algorithms, 1990, pp. 118?128."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"M. S. Paterson and F. F. Yao. Binary partitions with applications to hidden-surface removal and solid modelling.Proceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 23?32.","DOI":"10.1145\/73833.73836"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1109\/TC.1980.1675470","volume":"29","author":"R. B. Tilove","year":"1980","unstructured":"R. B. Tilove. Set membership classification: a unified approach to geometric intersection problems.IEEE Trans. Comput.,29 (1980), 874?883.","journal-title":"IEEE Trans. Comput."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1145\/358105.358195","volume":"27","author":"R. B. Tilove","year":"1984","unstructured":"R. B. Tilove. A null-object detection algorithm for constructive solid geometry.Comm. ACM,27 (1984), 684?694.","journal-title":"Comm. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190849.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01190849\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:09:10Z","timestamp":1734955750000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01190849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,5]]},"references-count":12,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,5]]}},"alternative-id":["BF01190849"],"URL":"https:\/\/doi.org\/10.1007\/bf01190849","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1995,5]]}}}