Separability of polyhedra for optimal filtering of spatial and constraint data

Abstract

The filtering method considered in this paper is based on approximation of a spatial object in d-dimensional space by the minimal convex polyhedron that encloses the object and whose facets are normal to preselected axes. These axes are not necessarily the standard coordinate axes; furthermore, their number is not determined by the dimension of the space. We optimize filtering by selecting optimal such axes based on a preprocessing analysis of stored objects or a sample thereof. The number of axes selected represents a trade-off between access time and storage overhead, as more axes usually lead to better filtering but require more overhead to store the associated access structures. We address the problem of minimizing the number of axes required to achieve a predefined quality of filtering and the reverse problem of optimizing the quality of filtering when the number of axes is fixed. In both cases we also show how to find an optimal collection of axes. To solve these problems, we introduce and study the key notion of separability classification, which is a general tool potentially useful in many applications of a computational geometry flavor. The approach is best suited to applications in which the spatial data is relatively static, some directions are more dominant than others, and the dimension of the space is not high; maps are a prime example.