| 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. |
