Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235542] of Pankaj K. Agarwal

Papers Published

  1. Beutel, A; Mølhave, T; Agarwal, PK; Boedihardjo, AP; Shine, JA, TerraNNI: Natural neighbor interpolation on a 3D grid using a GPU, GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (2011), pp. 64-73 [doi]
    (last updated on 2017/12/14)

    With modern focus on LiDAR technology the amount of topographic data, in the form of massive point clouds, has increased dramatically. Furthermore, due to the popularity of LiDAR, repeated surveys of the same areas are becoming more common. This trend will only increase as topographic changes prompt surveys over already scanned terrain, in which case we obtain large spatio-temporal data sets. In dynamic terrains, such as coastal regions, such spatio-temporal data can offer interesting insight into how the terrain changes over time. An initial step in the analysis of such data is to create a digital elevation model representing the terrain over time. In the case of spatio-temporal data sets those models often represent elevation on a 3D volumetric grid. This involves interpolating the elevation of LiDAR points on these grid points. In this paper we show how to efficiently perform natural neighbor interpolation over a 3D volumetric grid. Using a graphics processing unit (GPU), we describe different algorithms to attain speed and GPU-memory trade-offs. Our algorithm extends to higher dimensions. Our experimental results demonstrate that the algorithm is efficient and scalable. Categories and Subject. © 2011 ACM.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320