{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:34:57Z","timestamp":1763458497899,"version":"3.45.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,6,21]],"date-time":"2017-06-21T00:00:00Z","timestamp":1498003200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-08-1-0452,W911NF-07-1-0376"],"award-info":[{"award-number":["W911NF-08-1-0452,W911NF-07-1-0376"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["1P50-GM-08183-01"],"award-info":[{"award-number":["1P50-GM-08183-01"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000076","name":"Directorate for Biological Sciences","doi-asserted-by":"publisher","award":["CCF-09-40671,CCF-1012254,CNS-05-40347,IIS-07- 13498"],"award-info":[{"award-number":["CCF-09-40671,CCF-1012254,CNS-05-40347,IIS-07- 13498"]}],"id":[{"id":"10.13039\/100000076","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006752","name":"U.S. Army Corps of Engineers","doi-asserted-by":"publisher","award":["W9132V-11-C-0003"],"award-info":[{"award-number":["W9132V-11-C-0003"]}],"id":[{"id":"10.13039\/100006752","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2016,7]]},"abstract":"<jats:p>With modern focus on remote sensing technology, such as LiDAR, the amount of spatial data, in the form of massive point clouds, has increased dramatically. Furthermore, repeated surveys of the same areas are becoming more common. This trend will only increase as topographic changes prompt surveys over already scanned areas, in which case we obtain large spatiotemporal datasets.<\/jats:p>\n                  <jats:p>An initial step in the analysis of such spatial data is to create a digital elevation model representing the terrain, possibly over time. In the case of spatial (spatiotemporal, respectively) datasets, these models often represent elevation on a 2D (3D, respectively) grid. This involves interpolating the elevation of LiDAR points on these grid points.<\/jats:p>\n                  <jats:p>In this article, we show how to efficiently perform natural neighbor interpolation over a 2D and 3D grid. Using a graphics processing unit (GPU), we describe different algorithms to attain speed and GPU-memory tradeoffs. Our experimental results demonstrate that our algorithms not only are significantly faster than earlier ones but also scale to much bigger datasets that previous algorithms were unable to handle.<\/jats:p>","DOI":"10.1145\/2786757","type":"journal-article","created":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T09:02:27Z","timestamp":1466672547000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["TerraNNI"],"prefix":"10.1145","volume":"2","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Duke University, Durham NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Beutel","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"M\u00f8lhave","sequence":"additional","affiliation":[{"name":"SCALGO USA, Aarhus N, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_33"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2870-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336208"},{"key":"e_1_2_1_6_1","unstructured":"CGAL Development Team. 2014. Cgal Computational Geometry Algorithms Library. (2014). http:\/\/ www.cgal.org."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424360"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341012.1341049"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"M. de Berg M. van Kreveld M. Overmars and O. Schwarzkopf. 1997. Computational Geometry -- Algorithms and Applications. Springer Verlag.","DOI":"10.5555\/261226"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796607"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/174462.156635"},{"volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX\u201905)","author":"Fan Q.","key":"e_1_2_1_12_1","unstructured":"Q. Fan, A. Efrat, V. Koltun, S. Krishnan, and S. Venkatasubramanian. 2005. Hardware-assisted natural neighbor interpolation. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX\u201905)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"T. G. Farr P. A. Rosen E. Caro R. Crippen R. Duren S. Hensley M. Kobrick M. Paller E. Rodriguez L. Roth D. Seal S. Shaffer J. Shimada J. Umland M. Werner M. Oskin D. Burbank and D. Alsdorf. 2007. The shuttle radar topography mission. Reviews in Geophysics 45 (2007). http:\/\/dx.doi.org\/10.1029\/ 2005RG000183","DOI":"10.1029\/2005RG000183"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.stamet.2011.06.001"},{"key":"e_1_2_1_15_1","unstructured":"GRASS Development Team. 2014. GRASS GIS Homepage. http:\/\/www.baylor.edu\/grass\/. (2014)."},{"key":"e_1_2_1_16_1","unstructured":"R. Hemsley. 2009. Interpolation on a magnetic field. (2009). http:\/\/code.google.com\/p\/interpolate3d\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007528426688"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525363"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"L. Li and P. Revesz. 2002. A comparison of spatio-temporal interpolation methods. In Geographic Information Science. Vol. 2478. Springer 145--160.","DOI":"10.5555\/646933.710583"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"J. Mateu F. Montes and M. Fuentes. 2003. Recent advances in space-time statistics with applications to environmental data: An overview. Geophysical Research 108 8774 (2003).","DOI":"10.1029\/2003JD003819"},{"key":"e_1_2_1_21_1","unstructured":"E. Miller. 1997. Towards a 4d-GIS: Four dimensional interpolation utilizing kriging. In Innovations in GIS 4 Z. Kemp (Ed.). 181--197."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693799508902048"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geomorph.2005.06.001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1823854.1823878"},{"key":"e_1_2_1_25_1","volume-title":"LIDAR Data Retrieval Tool.","author":"AA.","year":"2014","unstructured":"NOAA. 2014. NOAA Coastal Services Center, LIDAR Data Retrieval Tool. (2014). http:\/\/csc-s-maps-q.csc.noaa.gov\/dataviewer\/viewer.html?keyword&equals;lidar."},{"key":"e_1_2_1_26_1","unstructured":"NVIDIA. 2010. CUDA Homepage. http:\/\/nvidia.com\/cuda. (2010). 3.0."},{"key":"e_1_2_1_27_1","unstructured":"S. J. Owen. 1992. An Implementation of Natural Neighbor Interpolation in Three Dimensions. Master\u2019s thesis."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01012.x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.27"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","unstructured":"S. Shekhar and H. Xiong (Eds.). 2008. Encyclopedia of GIS. Springer.","DOI":"10.5555\/1557182"},{"volume-title":"John Wiley & Sons","author":"Sibson R.","key":"e_1_2_1_31_1","unstructured":"R. Sibson. 1981. A brief description of natural neighbour interpolation. In Interpreting Multivariate Data, V. Barnet (Ed.). John Wiley & Sons, Chichester, 21--36."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(19981115)43:5<839::AID-NME423>3.0.CO;2-R"},{"key":"e_1_2_1_33_1","unstructured":"TPIE Development Team. 2014. Templated Portable I\/O Environment (TPIE). http:\/\/madalgo.au.dk\/tpie. (2014)."},{"key":"e_1_2_1_34_1","volume-title":"Contouring: A Guide to the Analysis and Display of Spatial Data.","author":"Watson D.","year":"1992","unstructured":"D. Watson. 1992. Contouring: A Guide to the Analysis and Display of Spatial Data. Oxford, Pergamon."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009662704779"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2345316.2345349"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786757","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2786757","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2786757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:29:24Z","timestamp":1763458164000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786757"}},"subtitle":["Natural Neighbor Interpolation on 2D and 3D Grids Using a GPU"],"short-title":[],"issued":{"date-parts":[[2016,6,21]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["10.1145\/2786757"],"URL":"https:\/\/doi.org\/10.1145\/2786757","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2016,6,21]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}