Box sort, a multidimensional binary sorting method for rectangular boxes, used for quick range searching (Q1100911)

In many geometrical applications data need to be sorted in more than one dimension to speed up running time, for example, the evaluation of set operations on polygons, and hidden-surface algorithms. We describe an efficient algorithm for doing this, which we call ``box sort''. Given are N boxes in an n-dimensional space. A box is a spatial region bounded by (hyper-)planes orthogonal to the coordinate axes. Box sort is a multidimensional sorting method for the N boxes, which allows us to perform quick range queries (``box searches'') with respect to these boxes. When the given N boxes are sufficiently scattered around the n- dimensional space, the box search for an arbitrary query box of the same order of size as the sorted boxes can be carried out in O(log N) time. The necessary memory requirement for box sort is invariably O(N).