{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:04:49Z","timestamp":1740107089724,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,21]],"date-time":"2020-11-21T00:00:00Z","timestamp":1605916800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,21]],"date-time":"2020-11-21T00:00:00Z","timestamp":1605916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Key Research and Development Project","award":["2016YFA0602200"],"award-info":[{"award-number":["2016YFA0602200"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1806205"],"award-info":[{"award-number":["U1806205"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis Comput"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00371-020-02011-3","type":"journal-article","created":{"date-parts":[[2020,11,21]],"date-time":"2020-11-21T11:02:31Z","timestamp":1605956551000},"page":"197-221","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["An adaptive and rapid 3D Delaunay triangulation for randomly distributed point cloud data"],"prefix":"10.1007","volume":"38","author":[{"given":"Tianyun","family":"Su","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haixing","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhendong","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinfang","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhen","family":"Jia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lin","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuanling","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Ding","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aiju","family":"Cui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,21]]},"reference":[{"key":"2011_CR1","doi-asserted-by":"crossref","unstructured":"Amenta, N., Choi, S., Rote, G.: Incremental constructions con BRIO. In: SCG\u201903 Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 211\u2013219 (2003)","DOI":"10.1145\/777792.777824"},{"key":"2011_CR2","unstructured":"Barber, C.B.: Computational geometry with imprecise data and arithmetic (1993)"},{"key":"2011_CR3","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.D., Devillers, O., Hornus, S.: Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension. In: Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, pp. 208\u2013216. ACM (2009)","DOI":"10.1145\/1542362.1542403"},{"issue":"20","key":"2011_CR4","doi-asserted-by":"publisher","first-page":"3407","DOI":"10.1002\/(SICI)1097-0207(19961030)39:20<3407::AID-NME5>3.0.CO;2-C","volume":"39","author":"H Borouchaki","year":"1996","unstructured":"Borouchaki, H., George, P., Lo, S.: Optimal Delaunay point insertion. Int. J. Numer. Methods Eng. 39(20), 3407\u20133437 (1996)","journal-title":"Int. J. Numer. Methods Eng."},{"issue":"1\u20132","key":"2011_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0045-7825(95)00854-1","volume":"128","author":"H Borouchaki","year":"1995","unstructured":"Borouchaki, H., Lo, S.: Fast Delaunay triangulation in three dimensions. Comput. Methods Appl. Mech. Eng. 128(1\u20132), 153\u2013167 (1995)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"issue":"2","key":"2011_CR6","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1093\/comjnl\/24.2.162","volume":"24","author":"A Bowyer","year":"1981","unstructured":"Bowyer, A.: Computing Dirichlet tessellations. Comput. J. 24(2), 162\u2013166 (1981)","journal-title":"Comput. J."},{"key":"2011_CR7","unstructured":"Buchin, K.: Organizing point sets: space-filling curves, Delaunay tessellations of random point sets, and flow complexes. Ph.D. thesis, Freie Universit\u00e4t Berlin (2008)"},{"key":"2011_CR8","doi-asserted-by":"crossref","unstructured":"Buchin, K.: Constructing Delaunay triangulations along space-filling curves. In: European Symposium on Algorithms, pp. 119\u2013130. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-04128-0_11"},{"key":"2011_CR9","doi-asserted-by":"crossref","unstructured":"Cao, T.T., Nanjappa, A., Gao, M., Tan, T.S.: A GPU accelerated algorithm for 3D Delaunay triangulation. In: Proceedings of the 18th meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, pp. 47\u201354 (2014)","DOI":"10.1145\/2556700.2556710"},{"key":"2011_CR10","unstructured":"Chao, Y., Wu, T., Wang, X., Zheng, G.: The computation of Delaunay triangulation of LiDAR point cloud based on GPU. In: 2015 23rd International Conference on Geoinformatics, pp. 1\u20134. IEEE (2015)"},{"issue":"3","key":"2011_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1111\/1467-8659.1230129","volume":"12","author":"P Cignoni","year":"2010","unstructured":"Cignoni, P., Montani, C., Perego, R., Scopigno, R.: Parallel 3D Delaunay triangulation. Comput. Graph. Forum 12(3), 129\u2013142 (2010)","journal-title":"Comput. Graph. Forum"},{"key":"2011_CR12","first-page":"793","volume":"6","author":"B Delaunay","year":"1934","unstructured":"Delaunay, B.: Sur la sph\u00e8re vide. a la m\u00e9moire de georges vorono. Bulletin de l\u2019Acad\u00e9mie des Sciences de l\u2019URSS. Classe des sciences math\u00e9matiques et naturelles 6, 793 (1934)","journal-title":"Classe des sciences math\u00e9matiques et naturelles"},{"issue":"02","key":"2011_CR13","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S0129054102001035","volume":"13","author":"O Devillers","year":"2003","unstructured":"Devillers, O.: The Delaunay hierarchy. Int. J. Found. Comput. Sci. 13(02), 163\u2013180 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2011_CR14","unstructured":"Devillers, O., Pion, S.: Efficient exact geometric predicates for Delaunay triangulations. In: Fifth Workshop on Algorithm Engineering & Experiments (2003)"},{"key":"2011_CR15","unstructured":"Devillers, O., Teillaud, M.: Perturbations and vertex removal in a 3D Delaunay triangulation. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2003)"},{"key":"2011_CR16","doi-asserted-by":"crossref","unstructured":"Dwyer, R.A.: Higher-dimensional Voronoi diagrams in linear expected time. In: The Fifth Annual Symposium (1989)","DOI":"10.1145\/73833.73869"},{"issue":"1\u20134","key":"2011_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S Fortune","year":"1987","unstructured":"Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2(1\u20134), 153\u2013174 (1987)","journal-title":"Algorithmica"},{"issue":"3","key":"2011_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/10867651.2002.10487560","volume":"7","author":"SF Frisken","year":"2002","unstructured":"Frisken, S.F., Perry, R.N.: Simple and efficient traversal methods for quadtrees and octrees. J. Graph. Tools 7(3), 1\u201311 (2002)","journal-title":"J. Graph. Tools"},{"issue":"7","key":"2011_CR19","doi-asserted-by":"publisher","first-page":"072001","DOI":"10.1007\/s11432-016-5588-7","volume":"59","author":"H Fu","year":"2016","unstructured":"Fu, H., Liao, J., Yang, J., Wang, L., Song, Z., Huang, X., Yang, C., Xue, W., Liu, F., Qiao, F.: The Sunway TaihuLight supercomputer: system and applications. Sci. China Inf. Sci. 59(7), 072001 (2016)","journal-title":"Sci. China Inf. Sci."},{"key":"2011_CR20","doi-asserted-by":"publisher","unstructured":"Funke, D., Sanders, P.: Parallel d-D Delaunay triangulations in shared and distributed memory, pp. 207\u2013217 (2017). https:\/\/doi.org\/10.1137\/1.9781611974768.17","DOI":"10.1137\/1.9781611974768.17"},{"issue":"2","key":"2011_CR21","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1093\/comjnl\/21.2.168","volume":"21","author":"PJ Green","year":"1978","unstructured":"Green, P.J., Sibson, R.: Computing Dirichlet tessellations in the plane. Comput. J. 21(2), 168\u2013173 (1978)","journal-title":"Comput. J."},{"key":"2011_CR22","doi-asserted-by":"crossref","unstructured":"Hilbert, D.: \u00dcber die stetige abbildung einer linie auf ein fl\u00e4chenst\u00fcck. In: Dritter Band: Analysis Grundlagen der Mathematik Physik Verschiedenes, pp. 1\u20132. Springer, Berlin (1935)","DOI":"10.1007\/978-3-662-38452-7_1"},{"issue":"8","key":"2011_CR23","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s00371-002-0173-z","volume":"18","author":"I Kolingerova","year":"2002","unstructured":"Kolingerova, I., Kohout, J.: Optimistic parallel Delaunay triangulation. Vis. Comput. 18(8), 511\u2013529 (2002)","journal-title":"Vis. Comput."},{"key":"2011_CR24","doi-asserted-by":"crossref","unstructured":"Lawson, C.: Software for C$$^1$$ surface interpolation. Math. Softw. III, 161\u2013194 (1977). https:\/\/doi.org\/10.1016\/B978-0-12-587260-7.50011-X","DOI":"10.1016\/B978-0-12-587260-7.50011-X"},{"issue":"4","key":"2011_CR25","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1093\/comjnl\/21.4.324","volume":"21","author":"BA Lewis","year":"1978","unstructured":"Lewis, B.A., Robinson, J.S.: Triangulation of planar regions with applications. Comput. J. 21(4), 324\u2013332 (1978)","journal-title":"Comput. J."},{"issue":"1","key":"2011_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10409-013-0001-x","volume":"29","author":"JF Liu","year":"2013","unstructured":"Liu, J.F., Yan, J.H., Lo, S.: A new insertion sequence for incremental Delaunay triangulation. Acta Mech. Sin. 29(1), 99\u2013109 (2013)","journal-title":"Acta Mech. Sin."},{"issue":"5\u20137","key":"2011_CR27","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s00371-009-0329-1","volume":"25","author":"X Liu","year":"2009","unstructured":"Liu, X., Gavrilova, M.L., Rokne, J.: Incorporating object-centered sampling and Delaunay tetrahedrization for visual hull reconstruction. Vis. Comput. 25(5\u20137), 381\u2013389 (2009)","journal-title":"Vis. Comput."},{"issue":"2","key":"2011_CR28","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1360\/132011-914","volume":"42","author":"Y Liu","year":"2012","unstructured":"Liu, Y., Guan, Z., Zhang, H., Zhang, Z.: Rapid 3d Delaunay inserting method towards large scale computing. Sci. Sin. Phys. Mech. Astron. 42(2), 192 (2012)","journal-title":"Sci. Sin. Phys. Mech. Astron."},{"issue":"439\u2013458","key":"2011_CR29","first-page":"56","volume":"52","author":"Y Liu","year":"2005","unstructured":"Liu, Y., Snoeyink, J.: A comparison of five implementations of 3D Delaunay tessellation. Combin. Comput. Geom. 52(439\u2013458), 56 (2005)","journal-title":"Combin. Comput. Geom."},{"key":"2011_CR30","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.cma.2012.05.009","volume":"237","author":"S Lo","year":"2012","unstructured":"Lo, S.: Parallel Delaunay triangulation in three dimensions. Comput. Methods Appl. Mech. Eng. 237, 88\u2013106 (2012)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"2011_CR31","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.finel.2012.08.005","volume":"63","author":"S Lo","year":"2013","unstructured":"Lo, S.: Delaunay triangulation of non-uniform point distributions by means of multi-grid insertion. Finite Elem. Anal. Des. 63, 8\u201322 (2013)","journal-title":"Finite Elem. Anal. Des."},{"key":"2011_CR32","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.finel.2014.07.002","volume":"90","author":"S Lo","year":"2014","unstructured":"Lo, S.: 3D Delaunay triangulation of non-uniform point distributions. Finite Elem. Anal. Des. 90, 113\u2013130 (2014)","journal-title":"Finite Elem. Anal. Des."},{"key":"2011_CR33","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.finel.2015.05.003","volume":"102","author":"S Lo","year":"2015","unstructured":"Lo, S.: 3D Delaunay triangulation of 1 billion points on a PC. Finite Elem. Anal. Des. 102, 65\u201373 (2015)","journal-title":"Finite Elem. Anal. Des."},{"key":"2011_CR34","unstructured":"Marot, C., Pellerin, J., Jonathan, L., Remacle, J.: Toward one billion tetrahedra per minute. In: 26th International Meshing Roundtable (2017)"},{"issue":"9","key":"2011_CR35","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1002\/nme.5987","volume":"117","author":"C Marot","year":"2019","unstructured":"Marot, C., Pellerin, J., Remacle, J.F.: One machine, one minute, three billion tetrahedra. Int. J. Numer. Methods Eng. 117(9), 967\u2013990 (2019)","journal-title":"Int. J. Numer. Methods Eng."},{"key":"2011_CR36","doi-asserted-by":"crossref","unstructured":"Navarro, C., Hitschfeld, N., Scheihing, E.: Quasi-Delaunay triangulations using GPU-based edge-flips. In: International Conference on Computer Vision, Imaging and Computer Graphics, pp. 36\u201349. Springer, Berlin (2013)","DOI":"10.1007\/978-3-662-45944-7_3"},{"issue":"2\u20133","key":"2011_CR37","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.comgeo.2004.03.009","volume":"28","author":"D Nave","year":"2004","unstructured":"Nave, D., Chrisochoides, N., Chew, L.P.: Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains. Comput. Geom. 28(2\u20133), 191\u2013215 (2004)","journal-title":"Comput. Geom."},{"key":"2011_CR38","volume-title":"The Science of Fractal Images","author":"HO Peitgen","year":"1988","unstructured":"Peitgen, H.O., Saupe, D.: The Science of Fractal Images. Springer, New York (1988)"},{"key":"2011_CR39","doi-asserted-by":"crossref","unstructured":"Peixinho, A.Z., Benato, B.C., Nonato, L.G., Falc\u00e3o, A.X.: Delaunay triangulation data augmentation guided by visual analytics for deep learning. In: 2018 31st SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), pp. 384\u2013391. IEEE, Brazil (2018)","DOI":"10.1109\/SIBGRAPI.2018.00056"},{"key":"2011_CR40","doi-asserted-by":"crossref","unstructured":"Quinn, J.A., Langbein, F.C., Martin, R.R., Elber, G.: Density-controlled sampling of parametric surfaces using adaptive space-filling curves. In: International Conference on Geometric Modeling and Processing, pp. 465\u2013484. Springer, Berlin (2006)","DOI":"10.1007\/11802914_33"},{"key":"2011_CR41","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.proeng.2015.10.118","volume":"124","author":"JF Remacle","year":"2015","unstructured":"Remacle, J.F., Bertrand, V., Geuzaine, C.: A two-level multithreaded Delaunay kernel. Proc. Eng. 124, 6\u201317 (2015)","journal-title":"Proc. Eng."},{"issue":"1","key":"2011_CR42","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/0141-1195(87)90043-X","volume":"9","author":"S Sloan","year":"1987","unstructured":"Sloan, S.: A fast algorithm for constructing Delaunay triangulations in the plane. Adv. Eng. Softw. (1978) 9(1), 34\u201355 (1987)","journal-title":"Adv. Eng. Softw. (1978)"},{"key":"2011_CR43","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cag.2015.07.019","volume":"54","author":"T Su","year":"2016","unstructured":"Su, T., Wang, W., Lv, Z., Wu, W., Li, X.: Rapid Delaunay triangulation for randomly distributed point cloud data using adaptive Hilbert curve. Comput. Graph. 54, 65\u201374 (2016)","journal-title":"Comput. Graph."},{"key":"2011_CR44","unstructured":"Teillaud, M.: Three dimensional triangulations in CGAL. EuroCG (1999)"},{"issue":"5","key":"2011_CR45","first-page":"736","volume":"19","author":"CT Tung","year":"2009","unstructured":"Tung, C.T.: Computing 2D Delaunay triangulation using GPU. Comp. Nus. Edu. Sg. 19(5), 736\u2013748 (2009)","journal-title":"Comp. Nus. Edu. Sg."},{"issue":"12","key":"2011_CR46","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1007\/s00371-010-0506-2","volume":"26","author":"LA Tychonievich","year":"2010","unstructured":"Tychonievich, L.A., Jones, M.: Delaunay deformable mesh for the weathering and erosion of 3D terrain. Vis. Comput. 26(12), 1485\u20131495 (2010)","journal-title":"Vis. Comput."},{"key":"2011_CR47","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.cag.2019.08.002","volume":"84","author":"W Wang","year":"2019","unstructured":"Wang, W., Su, T., Liu, H., Li, X., Jia, Z., Zhou, L., Song, Z., Ding, M.: Surface reconstruction from unoriented point clouds by a new triangle selection strategy. Comput. Graph. 84, 144\u2013159 (2019)","journal-title":"Comput. Graph."},{"issue":"2","key":"2011_CR48","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1093\/comjnl\/24.2.167","volume":"24","author":"DF Watson","year":"1981","unstructured":"Watson, D.F.: Computing the $$n$$-dimensional Delaunay tessellation with application to voronoi polytopes. Comput. J. 24(2), 167\u2013172 (1981)","journal-title":"Comput. J."},{"issue":"1","key":"2011_CR49","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. Proc. Lett. 93(1), 37\u201342 (2005)","journal-title":"Inf. Proc. Lett."}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-020-02011-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00371-020-02011-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-020-02011-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T04:07:40Z","timestamp":1697170060000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00371-020-02011-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,21]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["2011"],"URL":"https:\/\/doi.org\/10.1007\/s00371-020-02011-3","relation":{},"ISSN":["0178-2789","1432-2315"],"issn-type":[{"type":"print","value":"0178-2789"},{"type":"electronic","value":"1432-2315"}],"subject":[],"published":{"date-parts":[[2020,11,21]]},"assertion":[{"value":"27 October 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflicts of interest to this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}