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

Math @ Duke



Publications [#235531] of Pankaj K. Agarwal

Papers Published

  1. Beutel, A; Mølhave, T; Agarwal, PK, Natural neighbor interpolation based grid DEM construction using a GPU, GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (2010), pp. 172-181 [doi]
    (last updated on 2017/12/13)

    With modern LiDAR technology the amount of topographic data, in the form of massive point clouds, has increased dramatically. One of the most fundamental GIS tasks is to construct a grid digital elevation model (DEM) from these 3D point clouds. In this paper we present a simple yet very fast algorithm for constructing a grid DEM from massive point clouds using natural neighbor interpolation (NNI). We use a graphics processing unit (GPU) to significantly speed up the computation. To handle the large data sets and to deal with graphics hardware limitations clever blocking schemes are used to partition the point cloud. For example, using standard desktop computers and graphics hardware, we construct a high-resolution grid with 150 million cells from two billion points in less than thirty-seven minutes. This is about one-tenth of the time required for the same computer to perform a standard linear interpolation, which produces a much less smooth surface. © 2010 ACM.
ph: 919.660.2800
fax: 919.660.2821

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