Tri-cell—a data structure for spatial objects

摘要

We propose two methods based on the grid file approach. These methods are suitable for range queries on a collection of spatial objects. The idea is to transform spatial objects into points in a higher-dimensionality space [1]. However, the coordinates of the resulting points are correlated, forcing the original grid file method to poor performance. In this specific environment, we propose using triangular cells, instead of the traditional, rectangular ones. We illustrate the advantages of the proposed methods with examples, discuss the design details of each of the two variations, and present some preliminary performance results.