{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:56:53Z","timestamp":1725537413269},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_11","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"119-130","source":"Crossref","is-referenced-by-count":26,"title":["Constructing Delaunay Triangulations along Space-Filling Curves"],"prefix":"10.1007","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","first-page":"211","volume-title":"Proc. 19th Annu. ACM Sympos. Comput. Geom.","author":"N. Amenta","year":"2003","unstructured":"Amenta, N., Choi, S., Rote, G.: Incremental constructions con BRIO. In: Proc. 19th Annu. ACM Sympos. Comput. Geom., pp. 211\u2013219. ACM Press, New York (2003)"},{"issue":"3","key":"11_CR2","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00454-003-2870-4","volume":"31","author":"D. Attali","year":"2004","unstructured":"Attali, D., Boissonnat, J.-D.: A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete Comput. Geom.\u00a031(3), 369\u2013384 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/355921.355927","volume":"6","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Weide, B.W., Yao, A.C.: Optimal expected-time algorithms for closest-point problems. ACM Trans. Math. Softw.\u00a06, 563\u2013580 (1980)","journal-title":"ACM Trans. Math. Softw."},{"key":"11_CR4","unstructured":"Buchin, K.: Organizing Point Sets: Space-Filling Curves, Delaunay Tessellations of Random Point Sets, and Flow Complexes. PhD thesis, Free University Berlin (2007), http:\/\/www.diss.fu-berlin.de\/diss\/receive\/FUDISS_thesis_000000003494"},{"key":"11_CR5","unstructured":"Buchin, K., Mulzer, W.: Delaunay triangulations in ${O}(\\text{sort}(n))$ and other transdichotomous and hereditary algorithms in computational geometry. In: Proc. 50th Annu. IEEE Sympos. Found. Comput. Sci. (to appear, 2009)"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-540-39658-1_17","volume-title":"Algorithms - ESA 2003","author":"V. Damerow","year":"2003","unstructured":"Damerow, V., Meyer auf der Heide, F., R\u00e4cke, H., Scheideler, C., Sohler, C.: Smoothed motion complexity. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 161\u2013171. Springer, Heidelberg (2003)"},{"key":"11_CR7","unstructured":"Delage, C.: Spatial sorting. In: CGAL Editorial Board (eds), CGAL User and Reference Manual (2007)"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1142\/S021819599200007X","volume":"2","author":"O. Devillers","year":"1992","unstructured":"Devillers, O.: Randomization yields simple O(n log $^{\\mbox{*}}$ n) algorithms for difficult Omega(n) problems. Int. J. Comput. Geometry Appl.\u00a02(1), 97\u2013111 (1992)","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/PL00009234","volume":"22","author":"L. Devroye","year":"1998","unstructured":"Devroye, L., M\u00fccke, E., Zhu, B.: A note on point location in Delaunay triangulations of random points. Algorithmica\u00a022, 477\u2013482 (1998)","journal-title":"Algorithmica"},{"issue":"4","key":"11_CR10","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02574694","volume":"6","author":"R.A. Dwyer","year":"1991","unstructured":"Dwyer, R.A.: Higher-dimensional Voronoi diagrams in linear expected time. Discrete Comput. Geom.\u00a06(4), 343\u2013367 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Dense point sets have sparse Delaunay triangulations: or but not too nasty. In: Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 125\u2013134 (2002)","DOI":"10.1145\/378583.378636"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01199431","volume":"38","author":"D. Hilbert","year":"1891","unstructured":"Hilbert, D.: Ueber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck. Math. Ann.\u00a038, 459\u2013460 (1891)","journal-title":"Math. Ann."},{"key":"11_CR13","doi-asserted-by":"crossref","first-page":"275","DOI":"10.3233\/FI-1988-11305","volume":"11","author":"J. Katajainen","year":"1988","unstructured":"Katajainen, J., Koppinen, M.: Constructing Delaunay triangulations by merging buckets in quadtree order. Fundam. Inform.\u00a011, 275\u2013288 (1988)","journal-title":"Fundam. Inform."},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G.: Optimal search in planar subdivisions. SIAM J. Comput.\u00a012(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"key":"11_CR15","series-title":"MSRI Publications","first-page":"439","volume-title":"Combinatorial and Computational Geometry","author":"Y. Liu","year":"2005","unstructured":"Liu, Y., Snoeyink, J.: A comparison of five implementations of 3d Delaunay tesselation. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. MSRI Publications, vol.\u00a052, pp. 439\u2013458. Cambridge University Press, Cambridge (2005)"},{"issue":"1-2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0925-7721(98)00035-2","volume":"12","author":"E.P. M\u00fccke","year":"1999","unstructured":"M\u00fccke, E.P., Saias, I., Zhu, B.: Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations. Comput. Geom. Theory Appl.\u00a012(1-2), 63\u201383 (1999)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"4","key":"11_CR17","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1145\/76359.76361","volume":"36","author":"L.K. Platzman","year":"1989","unstructured":"Platzman, L.K., Bartholdi III, J.J.: Spacefilling curves and the planar travelling salesman problem. J. ACM\u00a036(4), 719\u2013737 (1989)","journal-title":"J. ACM"},{"issue":"3","key":"11_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0925-7721(96)00025-9","volume":"7","author":"P. Su","year":"1997","unstructured":"Su, P., Drysdale, R.: A comparison of sequential Delaunay triangulation algorithms. Comput. Geom. Theory Appl.\u00a07, 361\u2013386 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.ipl.2004.09.020","volume":"93","author":"S. Zhou","year":"2005","unstructured":"Zhou, S., Jones, C.B.: HCPO: an efficient insertion order for incremental Delaunay triangulation. Inf. Process. Lett.\u00a093(1), 37\u201342 (2005)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T19:09:21Z","timestamp":1685128161000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}