[Abstract]

LIDAR scans performed from planes have made it possible to cheaply produce high-resolution elevation models of entire countries, opening up new possibilities for geometric and physical analysis. The data is immense, though: even a small country with a surface area of 100’000 km^2 results in 100 billion data points at 1m resolution, so we need algorithms and data structures that are both fast and reduce the number of external-memory accesses.

We will discuss the problem of producing contour maps, the most intuitive and useful representation of terrains for the trained human eye, from the raw elevation data. The algorithm has been used at SCALGO to create contour maps for eight European countries, processing about 3 trillion elevation measurements. It produced good-looking contour maps that faithfully represent the actual landscape.

[Biography]

Otfried Cheong received his Ph.D. at FU Berlin in 1992. After his first position at Utrecht University he came to Postech from 1995 to 1997, and later held positions at Hong Kong University of Science & Technology, TU Eindhoven, and KAIST. Currently he is working with SCALGO on water flow simulations. He is on the editorial board of ‘Discrete & Computational Geometry’ and ‘Computational Geometry: Theory & Applications’, and was elected an ACM Distinguished Scientist in 2016. Since 1993, he has written and maintains the vector graphics editor ‘Ipe’.