{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T05:54:27Z","timestamp":1726206867143},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"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":[[1996,1]]},"DOI":"10.1007\/bf02716578","type":"journal-article","created":{"date-parts":[[2007,10,2]],"date-time":"2007-10-02T05:59:15Z","timestamp":1191304755000},"page":"35-61","source":"Crossref","is-referenced-by-count":31,"title":["Vertical decompositions for triangles in 3-space"],"prefix":"10.1007","volume":"15","author":[{"given":"M.","family":"de Berg","sequence":"first","affiliation":[]},{"given":"L. J.","family":"Guibas","sequence":"additional","affiliation":[]},{"given":"D.","family":"Halperin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"BF02716578_CR1","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1137\/0222051","volume":"22","author":"P. K. Agarwal","year":"1993","unstructured":"P. K. Agarwal and J. Matou\u0161ek. Ray shooting and parametric search.SIAM J. Comput., 22(4): 794\u2013806, 1993.","journal-title":"SIAM J. Comput."},{"key":"BF02716578_CR2","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/BF02574015","volume":"11","author":"P. K. Agarwal","year":"1994","unstructured":"P. K. Agarwal and J. Matou\u0161ek. On range searching with semialgebraic sets.Discrete Comput. Geom., 11:393\u2013418, 1994.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR3","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0097-3165(89)90032-0","volume":"52","author":"P. K. Agarwal","year":"1989","unstructured":"P. K. Agarwal, M. Sharir, and P. Shor. Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.J. Combin. Theory Ser. A, 52:228\u2013274, 1989.","journal-title":"J. Combin. Theory Ser. A"},{"issue":"2","key":"BF02716578_CR4","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02123007","volume":"10","author":"B. Aronov","year":"1990","unstructured":"B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air.Combinatorica, 10(2):137\u2013173, 1990.","journal-title":"Combinatorica"},{"key":"BF02716578_CR5","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BF02574371","volume":"12","author":"B. Aronov","year":"1994","unstructured":"B. Aronov and M. Sharir. Castles in the air revisited.Discrete Comput. Geom., 12:119\u2013150, 1994.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR6","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections.IEEE Trans. Comput., 28:643\u2013647, 1979.","journal-title":"IEEE Trans. Comput."},{"key":"BF02716578_CR7","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1137\/0213031","volume":"13","author":"B. Chazelle","year":"1984","unstructured":"B. Chazelle. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm.SIAM J. Comput., 13:488\u2013507, 1984.","journal-title":"SIAM J. Comput."},{"key":"BF02716578_CR8","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"B. Chazelle. Cutting hyperplanes for divide-and-conquer.Discrete Comput. Geom., 9:145\u2013158, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR9","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. Mach., 39:1\u201354, 1992.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02716578_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BFb0035760","volume-title":"Proc. 16th Internat. Colloq. Automata Lang. Program.","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. A singly-exponential stratification scheme for real semi-algebraic varieties and its applications.Proc. 16th Internat. Colloq. Automata Lang. Program., pp. 179\u2013192. Lecture Notes in Computer Science, vol. 372. Springer-Verlag, Berlin, 1989."},{"key":"BF02716578_CR11","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir. Lines in space: combinatorics, algorithms, and applications.Proc. 21st Ann. ACM Symp. Theory Comput., pp. 382\u2013393, 1989.","DOI":"10.1145\/73007.73044"},{"issue":"3","key":"BF02716578_CR12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry.Combinatorica, 10(3):229\u2013249, 1990.","journal-title":"Combinatorica"},{"key":"BF02716578_CR13","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique.Algorithmica, 1: 133\u2013162, 1986.","journal-title":"Algorithmica"},{"key":"BF02716578_CR14","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K. L. Clarkson","year":"1988","unstructured":"K. L. Clarkson. A randomized algorithm for closest-point queries.SIAM J. Comput., 17:830\u2013847, 1988.","journal-title":"SIAM J. Comput."},{"key":"BF02716578_CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. Clarkson","year":"1990","unstructured":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres.Discrete Comput. Geom., 5:99\u2013160, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR16","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387\u2013421, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0029813","volume-title":"Ray Shooting, Depth Orders and Hidden Surface Removal","author":"M. Berg de","year":"1993","unstructured":"M. de Berg.Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science, vol. 703. Springer-Verlag, Berlin, 1993."},{"key":"BF02716578_CR18","doi-asserted-by":"crossref","unstructured":"M. de Berg, K. Dobrindt, and O. Schwarzkopf. On lazy randomized incremental construction.Proc. 26th Ann. ACM Symp. Theory Comput., pp. 105\u2013114, 1994.","DOI":"10.1145\/195058.195113"},{"key":"BF02716578_CR19","doi-asserted-by":"crossref","unstructured":"M. de Berg, L. J. Guibas, and D. Halperin. Vertical Decompositions for Triangles in 3-Space. Technical Report UU-CS-1994-29, Utrecht University, 1994.","DOI":"10.1145\/177424.177427"},{"key":"BF02716578_CR20","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/BF01377182","volume":"12","author":"M. Berg de","year":"1994","unstructured":"M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient ray shooting and hidden surface removal.Algorithmica, 12:30\u201353, 1994.","journal-title":"Algorithmica"},{"key":"BF02716578_CR21","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF02187734","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner. The upper envelope of piecewise linear functions: tight complexity bounds in higher dimensions.Discrete Comput. Geom., 4:337\u2013343, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR22","doi-asserted-by":"crossref","unstructured":"M. Goodrich and R. Tamassia. Dynamic trees and dynamic point location.Proc. 23rd Ann. ACM Symp. Theory Comput., pp. 523\u2013533, 1991.","DOI":"10.1145\/103418.103472"},{"key":"BF02716578_CR23","series-title":"Lecture Notes in Computer Science","first-page":"8","volume-title":"Proc. 19th Ann. IEEE Symp. Found. Comput. Sci.","author":"L. J. Guibas","year":"1978","unstructured":"L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees.Proc. 19th Ann. IEEE Symp. Found. Comput. Sci., pp. 8\u201321. Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1978."},{"key":"BF02716578_CR24","doi-asserted-by":"crossref","unstructured":"D. Halperin and M. Sharir. Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment.Proc. 34th Ann. Symp. Found. Comput. Sci., pp. 382\u2013391, 1993.","DOI":"10.1109\/SFCS.1993.366849"},{"key":"BF02716578_CR25","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:151\u2013177, 1986.","journal-title":"Combinatorica"},{"key":"BF02716578_CR26","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl. Epsilon-nets and simplex range queries.Discrete Comput. Geom., 2:127\u2013151, 1987.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR27","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1090\/dimacs\/006\/08","volume-title":"Discrete and Computational Geometry: Papers from the DIMACS Special Year","author":"J. Heintz","year":"1991","unstructured":"J. Heintz, T. Recio, and M.-F. Roy. Algorithms in real algebraic geometry and applications to computational geometry. In: J. E. Goodman, R. Pollack, and W. Steiger, ed.,Discrete and Computational Geometry: Papers from the DIMACS Special Year, pp. 137\u2013163. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 6. American Mathematical Society, Providence, RI, 1991."},{"key":"BF02716578_CR28","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J. Hershberger","year":"1989","unstructured":"J. Hershberger. Finding the upper envelope ofn line segments inO(n logn) time.Inform. Process. Lett., 33:169\u2013174, 1989.","journal-title":"Inform. Process. Lett."},{"key":"BF02716578_CR29","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek. Range searching with efficient hierarchical cuttings.Discrete Comput. Geom. 10:157\u2013182, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR30","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Hidden surface removal with respect to a moving point.Proc. 23rd Ann. ACM Symp. Theory Comput., pp. 512\u2013522, 1991.","DOI":"10.1145\/103418.103471"},{"key":"BF02716578_CR31","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Randomized multidimensional search trees: further results in dynamic sampling.Proc. 32nd Ann. IEEE Symp. Found. Comput. Sci., pp. 216\u2013227, 1991.","DOI":"10.1109\/SFCS.1991.185371"},{"key":"BF02716578_CR32","doi-asserted-by":"crossref","unstructured":"M. Overmars and M. Sharir. Output-sensitive hidden surface removal.Proc. 30th Ann. IEEE Symp. Found. Comput. Sci., pp. 598\u2013603, 1989.","DOI":"10.1109\/SFCS.1989.63541"},{"key":"BF02716578_CR33","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":"BF02716578_CR34","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1137\/0221020","volume":"21","author":"F. P. Preparata","year":"1992","unstructured":"F. P. Preparata and R. Tamassia. Efficient point location in a convex spatial cell-complex.SIAM J. Comput., 21:267\u2013280, 1992.","journal-title":"SIAM J. Comput."},{"key":"BF02716578_CR35","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF02574384","volume":"12","author":"M. Sharir","year":"1994","unstructured":"M. Sharir. Almost tight upper bounds for lower envelopes in higher dimensions.Discrete Comput. Geom., 12:327\u2013345, 1994.","journal-title":"Discrete Comput. Geom."},{"key":"BF02716578_CR36","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1987","unstructured":"R. E. Tarjan.Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1987."},{"key":"BF02716578_CR37","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF02187894","volume":"3","author":"A. Wiernik","year":"1988","unstructured":"A. Wiernik and M. Sharir. Planar realizations of nonlinear Davenport-Schinzel sequences by segments.Discrete Comput. Geom., 3:15\u201347, 1988.","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02716578.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02716578\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02716578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T09:57:19Z","timestamp":1558432639000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02716578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["BF02716578"],"URL":"https:\/\/doi.org\/10.1007\/bf02716578","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}