摘要:
Spatial data structures form a core ingredient of many geometric algorithms, both in theory and in practice. Many of these data structures, especially the ones used in practice, are based on partitioning the underlying space (examples are binary space partitions and decompositions of polygons) or partitioning the set of objects (examples are bounding-volume hierarchies). The efficiency of such data structures-and, hence, of the algorithms that use them-depends on certain characteristics of the partitioning. For example the performance of many algorithms that use binary space partitions ( BSP s) depends on the size of the BSP s. Similarly, the performance of answering range queries using bounding-volume hierarchies ( BVH s) depends on the so-called crossing number that can be associated with the partitioning on which the BVH is based. Much research has been done on the problem of computing partitioning whose characteristics are good in the worst case. In this thesis, we studied the problem from a different point of view, namely instance-optimality. In particular, we considered the following question: given a class of geometric partitioning structures-like BSP s, simplicial partition, polygon triangulations,... -and a cost function-like size or crossing number-can we design an algorithm that computes a structure whose cost is optimal or close to optimal for any input instance (rather than only worst-case optimal). We studied the problem of finding optimal data structures for some of the most important spatial data structures. As an example having a set of n points and an input parameter r, It has been proved that there are input sets for which any simplicial partition has crossing number Ω( √ r). It has also been shown that for any set of n input points and the parameter r one can make a simplicial partition with stabbing number O( √ r). However, there are input point sets for which one can make simplicial partitions with lower stabbing number. As an example when the