{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T05:21:32Z","timestamp":1768713692117,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,7,1]],"date-time":"2006-07-01T00:00:00Z","timestamp":1151712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            We show how to greatly accelerate algorithms that compute Delaunay triangulations of huge, well-distributed point sets in 2D and 3D by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing\n            <jats:italic>spatial finalization<\/jats:italic>\n            into point streams: we partition space into regions, and augment a stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop with two hard drives. This is a factor of twelve faster than the previous fastest out-of-core Delaunay triangulation software.\n          <\/jats:p>","DOI":"10.1145\/1141911.1141992","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"1049-1056","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Streaming computation of Delaunay triangulations"],"prefix":"10.1145","volume":"25","author":[{"given":"Martin","family":"Isenburg","sequence":"first","affiliation":[{"name":"University of California at Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuanxin","family":"Liu","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Shewchuk","sequence":"additional","affiliation":[{"name":"University of California at Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_33"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777824"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001580"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008262"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.162"},{"key":"e_1_2_2_6_1","volume-title":"Second Symposium on Voronoi Diagrams, 184--195","author":"Buchin K.","year":"2005","unstructured":"Buchin , K. 2005 . Constructing Delaunay triangulations along space-filling curves . In Second Symposium on Voronoi Diagrams, 184--195 .]] Buchin, K. 2005. Constructing Delaunay triangulations along space-filling curves. In Second Symposium on Voronoi Diagrams, 184--195.]]"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(97)00082-1"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217052"},{"key":"e_1_2_2_10_1","series-title":"Lecture Notes Series on Computing","volume-title":"Computing in Euclidean Geometry, D.-Z. Du and F","author":"Fortune S.","unstructured":"Fortune , S. 1992. Voronoi diagrams and Delaunay triangulations . In Computing in Euclidean Geometry, D.-Z. Du and F . Hwang, Eds., vol. 1 of Lecture Notes Series on Computing . World Scientific , Singapore , 193--233.]] Fortune, S. 1992. Voronoi diagrams and Delaunay triangulations. In Computing in Euclidean Geometry, D.-Z. Du and F. Hwang, Eds., vol. 1 of Lecture Notes Series on Computing. World Scientific, Singapore, 193--233.]]"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620020112"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882366"},{"key":"e_1_2_2_13_1","volume-title":"Visualization '05 Proceedings, 231--238","author":"Isenburg M.","unstructured":"Isenburg , M. , and Lindstrom , P . 2005. Streaming meshes . In Visualization '05 Proceedings, 231--238 .]] Isenburg, M., and Lindstrom, P. 2005. Streaming meshes. In Visualization '05 Proceedings, 231--238.]]"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2003.1250408"},{"key":"e_1_2_2_15_1","volume-title":"IFIP 12th World Computer Congress, North-Holland, J. van Leeuwen, Ed.","volume":"12","author":"Karp R. M.","year":"1992","unstructured":"Karp , R. M. 1992 . On-line algorithms versus off-line algorithms: How much is it worth to know the future? In IFIP 12th World Computer Congress, North-Holland, J. van Leeuwen, Ed. , vol. A- 12 of IFIP Transactions, 416--429.]] Karp, R. M. 1992. On-line algorithms versus off-line algorithms: How much is it worth to know the future? In IFIP 12th World Computer Congress, North-Holland, J. van Leeuwen, Ed., vol. A-12 of IFIP Transactions, 416--429.]]"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","first-page":"275","DOI":"10.3233\/FI-1988-11305","article-title":"Constructing Delaunay triangulations by merging buckets in quadtree order","author":"Katajainen J.","year":"1988","unstructured":"Katajainen , J. , and Koppinen , M. 1988 . Constructing Delaunay triangulations by merging buckets in quadtree order . Fundamenta Informaticae XI , 11, 275 -- 288 .]] Katajainen, J., and Koppinen, M. 1988. Constructing Delaunay triangulations by merging buckets in quadtree order. Fundamenta Informaticae XI, 11, 275--288.]]","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_2_17_1","volume-title":"Algorithms for Memory Hierarchies, LNCS 2625","author":"Kumar P.","unstructured":"Kumar , P. 2003. Cache oblivious algorithms . In Algorithms for Memory Hierarchies, LNCS 2625 , U. Meyer, P. Sanders, and J. Sibeyn, Eds. Springer-Verlag , 193--212.]] Kumar, P. 2003. Cache oblivious algorithms. In Algorithms for Memory Hierarchies, LNCS 2625, U. Meyer, P. Sanders, and J. Sibeyn, Eds. Springer-Verlag, 193--212.]]"},{"key":"e_1_2_2_18_1","volume-title":"Software for C1 surface interpolation","author":"Lawson C. L.","unstructured":"Lawson , C. L. 1977. Software for C1 surface interpolation . In Mathematical Software III, J. R. Rice, Ed. Academic Press , New York , 161--194.]] Lawson, C. L. 1977. Software for C1 surface interpolation. In Mathematical Software III, J. R. Rice, Ed. Academic Press, New York, 161--194.]]"},{"key":"e_1_2_2_19_1","unstructured":"Liu Y. and \n      Snoeyink J\n  . \n  2005\n  . A comparison of five implementations of 3D Delaunay tessellation. In Combinatorial and Computational Geometry vol. \n  52\n   of \n  MSRI Publications\n  . \n  Cambridge 435--453.]]  Liu Y. and Snoeyink J. 2005. A comparison of five implementations of 3D Delaunay tessellation. In Combinatorial and Computational Geometry vol. 52 of MSRI Publications. Cambridge 435--453.]]"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Okabe A. Boots B. Sugihara K. and Chiu S. N. 2000. Spatial tessellations: Concepts and applications of Voronoi diagrams 2nd ed. Wiley New York.]]   Okabe A. Boots B. Sugihara K. and Chiu S. N. 2000. Spatial tessellations: Concepts and applications of Voronoi diagrams 2nd ed. Wiley New York.]]","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_2_21_1","volume-title":"Visualization '05 Proc., 239--246","author":"Pajarola R.","year":"2005","unstructured":"Pajarola , R. 2005 . Stream-processing points . In Visualization '05 Proc., 239--246 .]] Pajarola, R. 2005. Stream-processing points. In Visualization '05 Proc., 239--246.]]"},{"key":"e_1_2_2_22_1","unstructured":"Quillin M. 2002. Flood plain maps better but late---years late March 11. Raleigh News & Observer.]]  Quillin M. 2002. Flood plain maps better but late---years late March 11. Raleigh News & Observer.]]"},{"key":"e_1_2_2_23_1","volume-title":"Graphics Gems","author":"Shaffer C. A.","unstructured":"Shaffer , C. A. 1990. Fast circle-rectangle intersection checking . In Graphics Gems . Academic Press Professional, Inc. , San Diego, CA, USA , 51--53.]] Shaffer, C. A. 1990. Fast circle-rectangle intersection checking. In Graphics Gems. Academic Press Professional, Inc., San Diego, CA, USA, 51--53.]]"},{"key":"e_1_2_2_24_1","volume-title":"16th Annual Symposium on Foundations of Computer Science, IEEE Press, 151--162","author":"Shamos M. I.","unstructured":"Shamos , M. I. , and Hoey , D . 1975. Closest-point problems . In 16th Annual Symposium on Foundations of Computer Science, IEEE Press, 151--162 .]] Shamos, M. I., and Hoey, D. 1975. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science, IEEE Press, 151--162.]]"},{"key":"e_1_2_2_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering","author":"Shewchuk J. R.","year":"1996","unstructured":"Shewchuk , J. R. 1996 . Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering , M. C. Lin and D. Manocha, Eds., vol. 1148 of Lecture Notes in Computer Science . Springer-Verlag , Berlin, May, 203--222.]] Shewchuk, J. R. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, Eds., vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, May, 203--222.]]"},{"key":"e_1_2_2_26_1","first-page":"3","article-title":"Adaptive precision floating-point arithmetic and fast robust geometric predicates","volume":"18","author":"Shewchuk J. R.","year":"1997","unstructured":"Shewchuk , J. R. 1997 . Adaptive precision floating-point arithmetic and fast robust geometric predicates . Discrete & Computational Geometry 18 , 3 (Oct.), 305--363.]] Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (Oct.), 305--363.]]","journal-title":"Discrete & Computational Geometry"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276894"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220286"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.167"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073278"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1141992","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1141911.1141992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:24Z","timestamp":1750259664000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1141992"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1141911.1141992"],"URL":"https:\/\/doi.org\/10.1145\/1141911.1141992","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}