3D Range Searching Using Chain Decomposition

Abstract

We propose the first data structure based on untangled monotonic chains for or- thogonal range searching in 3-dimensional space. The idea is an extension of the 2-dimensional chain partition algorithm proposed by Arroyuelo et al. (Untangled monotonic chains and adaptive range search, Theoretical Computer Science, 412(32), 2011). We also provide an improved algorithm for the chain untangling process, which in practice runs 25% percent faster than the untangling algorithm proposed in the experimental studies of Claude et al. (Range queries over untangled chains, SPIRE, Springer 2010). In the experimental evaluations, we first re-examined the experimen- tal studies conducted by Claude et al. for the 2-dimensional range searching algorithm based on untangled monotonic chains and found that the k-d tree implementation in CGAL, which is used as a reference for the experimental evaluation previously, is inefficient for the task at hand. Therefore, we implemented k-d trees ourselves and compared them against two range searching methods based on untangled chains. The experimental results showed that, in 2D, the performance of range searching methods based on untangled monotonic chains is similar to that of the k-d tree, which contra- dicts the experimental results of Claude et al. We then performed similar experimental studies in three dimensions. In 3D, the chain-decomposition-based range searching methods were unable to match the performance of k-d trees, which is mainly due to the difficulties in decomposing point sets into monotonic chains: our approaches either generated too many chains or used too much time to construct when the point set was large.