{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:42Z","timestamp":1725559002488},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_11","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T13:27:29Z","timestamp":1279027649000},"page":"114-126","source":"Crossref","is-referenced-by-count":0,"title":["Matching Polyhedral Terrains Using Overlays of Envelopes"],"prefix":"10.1007","author":[{"given":"Vladlen","family":"Koltun","sequence":"first","affiliation":[]},{"given":"Carola","family":"Wenk","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Har-Peled, S., Sharir, M., Wang, Y.: Hausdorff distance under translation for points, disks, and balls. In: Proc. Symp. Comp. Geom (2003)","DOI":"10.1145\/777833.777835"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02716576","volume":"15","author":"P.K. Agarwal","year":"1996","unstructured":"Agarwal, P.K., Schwarzkopf, O., Sharir, M.: The overlay of lower envelopes and its applications. Discrete and Computational Geometry\u00a015, 1\u201313 (1996)","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/B978-044482537-7\/50003-6","volume-title":"Handbook of Computational Geometry","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 49\u2013119. Elsevier Science Publishers B.V. North-Holland, Amsterdam (2000)"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Alt, H., Guibas, L.: Discrete geometric shapes: Matching, interpolation, and approximation \u2013 a survey. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, Elsevier Science Publishers B.V. North-Holland (2000)","DOI":"10.1016\/B978-044482537-7\/50004-8"},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0925-7721(95)00007-0","volume":"5","author":"J.-D. Boissonnat","year":"1996","unstructured":"Boissonnat, J.-D., Dobrindt, K.: On-line construction of the upper envelope of triangles and surface patches in three dimensions. Comput. Geom. Theory Appl.\u00a05, 303\u2013320 (1996)","journal-title":"Comput. Geom. Theory Appl."},{"key":"11_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172998","volume-title":"Algorithmic Geometry","author":"J.-D. Boissonnat","year":"1998","unstructured":"Boissonnat, J.-D., Yvinec, M.: Algorithmic Geometry. Cambridge University Press, Cambridge (1998)"},{"issue":"2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom.\u00a09(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K.L. Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM Journal on Computing\u00a017, 830\u2013847 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF02716578","volume":"15","author":"M. Berg de","year":"1996","unstructured":"de Berg, M., Guibas, L.J., Halperin, D.: Vertical decompositions for triangles in 3-space. Discrete Comput. Geom.\u00a015, 35\u201361 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF02187734","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H.: The upper envelope of piecewise linear functions: Tight complexity bounds in higher dimensions. Discrete and Comp. Geom.\u00a04, 337\u2013343 (1989)","journal-title":"Discrete and Comp. Geom."},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L., Sharir, M.: The upper envelope of piecewise linear functions: algorithms and applications. Discr. Comp. Geom.\u00a04, 311\u2013336 (1989)","journal-title":"Discr. Comp. Geom."},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J. Hershberger","year":"1989","unstructured":"Hershberger, J.: Finding the upper envelope of n line segments in O(n log n) time. Inform. Process. Lett.\u00a033, 169\u2013174 (1989)","journal-title":"Inform. Process. Lett."},{"key":"11_CR13","unstructured":"Koltun, V., Sharir, M.: The partition technique for overlays of envelopes. SIAM Journal on Computing (to appear)"},{"key":"11_CR14","unstructured":"Koltun, V., Wenk, C.: Matching polyhedral terrains using overlays of envelopes, http:\/\/www.cs.berkeley.edu\/~vladlen\/linear-overlays-full.zip"},{"key":"11_CR15","first-page":"271","volume-title":"Discr. Comp. Geom","author":"C. Lee","year":"1997","unstructured":"Lee, C.: Subdivisions and triangulations of polytopes. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Discr. Comp. Geom, pp. 271\u2013290. CRC Press, Boca Raton (1997)"},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom.\u00a010(2), 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"11_CR17","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM\u00a030(4), 852\u2013865 (1983)","journal-title":"J. ACM"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02187732","volume":"4","author":"J. Pach","year":"1989","unstructured":"Pach, J., Sharir, M.: The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: combinatorial analysis. Discrete Comput. Geom.\u00a04, 291\u2013309 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02574384","volume":"12","author":"M. Sharir","year":"1994","unstructured":"Sharir, M.: Almost tight upper bounds for lower envelopes in higher dimensions. Discrete and Computational Geometry\u00a012, 327\u2013345 (1994)","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR20","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/BF02712877","volume":"16","author":"B. Tagansky","year":"1996","unstructured":"Tagansky, B.: A new technique for analyzing substructures in arrangements of piecewise linear surfaces. Discrete and Computational Geometry\u00a016, 455\u2013479 (1996)","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR22","unstructured":"Wenk, C.: Shape Matching in Higher Dimensions. Ph.D. thesis, Free University Berlin, Berlin, Germany (2002)"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF02187894","volume":"3","author":"A. Wiernik","year":"1988","unstructured":"Wiernik, A., Sharir, M.: Planar realizations of nonlinear Davenport-Schinzel sequences by segments. Discrete Comput. Geom.\u00a03, 15\u201347 (1988)","journal-title":"Discrete Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:21:39Z","timestamp":1605741699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}