An extended cell splitting algorithm for spatial databases
Masayuki Tanaka, K. Kaneko, Yingliang Lu, Akifumi Makinouchi · 2004
The cell-splitting problem is an important problem in computational geometry and the spatial database and constraint database fields. Spatial operations such as intersection and difference are based on splitting cells with hyperplanes. This paper proposes an algorithm to split both bounded and unbounded cells with hyperplanes in any dimension. The previous algorithm works only for bounded objects because this algorithm assumes that all k-polytopes are connected to more than two (k-1)-polytopes. The newly proposed algorithm considers the number of (k-1)-polytopes in the evaluation process and applies different polytope splitting and position vector creation algorithms. This makes it possible to compute an unbounded cell. The implementation and evaluation of the proposed algorithm are presented.