Optimization of polyhedral terrains


Update content

Title Optimization of polyhedral terrains
Period 07 / 2005 - 10 / 2009
Status Completed
Dissertation Yes
Research number OND1308131
Data Supplier Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)


Geometric computation for cartography, realistic terrain modeling, and delineation of imprecise geographic regions all require geometric algorithms where several geometric criteria must be met simultaneously. This proposal addresses such computational problems by designing new algorithms with efficiency analyses and approximation factor proofs. In cartographic generalization, for example, spatial aggregation of two regions asks for a new, connected region that has a natural shape, but while adding as little area in the connection as possible. For metro maps, stations must be close to their true location, connections may only have few, restricted-orientation links, and connections may not intersect. Many other examples can be given in which there are several criteria that determine a good solution. In terrain modeling, conversion of an elevation grid to a polyhedral terrain (triangulation) is an important operation. The resulting triangulation is often the Delaunay triangulation because it maximizes the smallest angle used. Therefore, it is good for height interpolation. But other criteria like slope fidelity and avoiding artificial dams are also important. These problems will be studied using higher-order Delaunay triangulations. Geometric optimization problems are often NP-hard, or an optimal solution is incomputable. Allowing additional constraints will not reduce asymptotic running time. Instead, problems will become essentially more difficult. Therefore, the focus will be on efficient approximation algorithms with guaranteed performance factors. The starting point is problems with two geometric constraints where one constraint must be met using a threshold, while the other constraint is optimized.

Abstract (NL)

Rodrigo Silveira ontwikkelde nieuwe methodes die gebruikt kunnen worden om preciezere en betrouwbaardere terreinmodellen te produceren. Een digitaal terreinmodel is een computerrepresentatie van een terrein uit de echte wereld. Terreinmodellen zijn belangrijk in geografische informatiesystemen. Een terreinmodel kan bijvoorbeeld gebruikt worden om regen te simuleren en om te voorspellen welke gebieden vatbaar zijn voor overstroming. Eén van de belangrijkste manieren om een terrein te representeren is een triangulatie (driehoeksmeting): punten worden gemeten in het echte terrein, en verbonden door driehoeken die het hele terrein overspannen. Wanneer triangulaties gebruikt worden voor terreinmodellering zijn een aantal aspecten van de triangulatie belangrijk. Lange en dunne driehoeken moeten bijvoorbeeld worden vermeden. Zo zijn er meer criteria waaraan een triangulatie moet voldoen om een redelijk model voor een terrein te vormen. Om een voorbeeld te noemen, terreinen die gevormd zijn door natuurlijke processen hebben weinig kuilen. Afhankelijk van de gebruikte triangulatie kan het aantal kuilen in een model veel hoger zijn. Als zo'n model wordt gebruikt voor hydrologische simulaties, kunnen deze kuilen de resultaten ernstig verstoren. In dit geval zijn de kuilen een voorbeeld van artefacten van de triangulatie die zouden moeten worden vermeden. Rodrigo Silveira presenteert in zijn proefschrift nieuwe automatische methodes om triangulaties te vinden met goedgevormde driehoeken, en tegelijkertijd zo weinig mogelijk artefacten.

Related organisations

Related people

Supervisor Prof.dr. R.C. Veltkamp
Co-supervisor Prof.dr. M.J. van Kreveld
Project leader Dr. R.W. van Oostrum
Doctoral/PhD student Dr. M. Löffler
Doctoral/PhD student Dr. R.I. Silveira


A90000 Fundamental research
D11500 Geometry, topology
D16200 Software, algorithms, control systems
D16400 Information systems, databases

Go to page top
Go back to contents
Go back to site navigation