Alex Beutel, Thomas Mølhave, and Pankaj Agarwal Win Best Paper Award

December 01, 2010

<div class=\"NewsPhotoWrapper\" style=\"width:285px; margin-top:5px; \">

<div class=\"OneNewsPhoto\">
<img src=\"/web_resources/photos_news/361_056010_beutel_csurf014_350w.jpg\" style=\"width:285px;\"/>
<p class=\"NewsPhotoCaption\">Prof. Pankaj Agarwal, Alex Beutel, Thomas Mølhave

<div class=\"OneNewsPhoto\">
<img src=\"/web_resources/photos_news/361_3d_550w.png\" style=\"width:285px;\"/>
<p class=\"NewsPhotoCaption\">Computing Voronoi diagrams for the construction of the 3D model of a terrain

<div class=\"OneNewsPhoto\">
<img src=\"/web_resources/photos_news/361_Afghanistan_0_5m_from_tin_1_cut.png\" style=\"width:285px;\"/>
<p class=\"NewsPhotoCaption\">A 3D terrain model constructed using the algorithm

Alex Beutel, a senior CS and physics double major at Duke, had never heard of a best paper award. But at the banquet for the 18th annual ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems in November, the premiere GIS symposium, that was about to change.

\"I was beyond in shock,\" says Beutel. \"It was a great surprise, and a great honor.\" Beutel, along with CS postdoc Thomas Mølhave and advisor Professor Pankaj Agarwal, took home the best paper award for their work, \"Natural Neighbor Interpolation Based Grid DEM Construction Using a GPU.\" The paper presents a simple yet fast algorithm for constructing digital 3D terrain models from large amounts of topographic data.

Currently, planes use a sophisticated laser technology to fly over terrain and collect data about the ground below. But it has been challenging to use the massive data sets to construct high-resolution 3D models, valuable for practical applications like flood mapping and navigation.

Using a graphics processing unit -- available on modern PCs and originally used for high-end 3D rendering -- to speed up the computation, the trio designed an algorithm that computes the height of the underlying terrain on a grid of desired resolution, using a special method of spatial interpolation. Their technique produces high-quality digital 3D models of terrains in one-tenth of the time of older systems. The work is part of a project funded by US Army Research Office.

\"Alex was critical to the success of this work,\" says Agarwal. \"Besides being smart and creative, he brought certain mathematical and analytical skills that are not common in a typical CS student.\"

Beutel, who hopes to begin a PhD in computer science in the fall, continues to work on the algorithm with M�lhave and Agarwal, now extending the research to include temporal data to model how a terrain changes over time.