KNAW

Research

Optimal Geometric Data Structures

Pagina-navigatie:


Update content


Title Optimal Geometric Data Structures
Period 11 / 2007 - 01 / 2012
Status Completed
Dissertation Yes
Research number OND1346640
Data Supplier NWO

Abstract

Spatial data structures play a fundamental role in computational geometry and its applications. Many of these data structures, especially the ones that are used in practice, are based on geometric structures such as space partitionings or coverings of the objects by bounding volumes. The performance of the resulting data structures---the amount of storage they need and the time it takes to perform queries---depends directly on certain properties of the underlying geometric structure. Hence, a lot of research in computational geometry has gone into designing algorithms that construct geometric structures with good properties. Most existing research in this area, however, has focussed on geometric structures whose properties are good in the worst-case. This means that when the actual input happens to be much easier than a worst-case input, the performance of the resulting data structure can be far from optimal. Therefore we propose to study algorithms for constructing geometric structures that are optimal, or provably close to optimal, for any input, leading to spatial data structures that are as efficient as possible for the actual data they store.

Abstract (NL)

Ruimtelijke data spelen een belangrijke rol in veel gebieden van de informatica-denk aan robotica, geografische informatiesystemen, CAD/CAM, of computer graphics. In veel van die gebieden is het nodig om de data op te slaan in een datastructuur waarmee bepaalde zoekacties snel kunnen worden uitgevoerd. Vaak zijn deze structuren er vooral op gericht om moeilijke data sets zo effici¨ent mogelijk te behandelen, en profiteren ze er weinig van als de data set in de specifieke toepassing relatief makkelijk is. In dit onderzoek willen we daarom structuren ontwerpen die alle data sets op een optimale manier behandelen.

Related organisations

Related people

Supervisor Prof.dr. M.T. de Berg
Doctoral/PhD student Dr. A. Khosravi Dehkordi

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