(original) (raw)

TY - JOUR AU - Houthuys, Piet PY - 1987 DA - 1987/12/01 TI - Box Sort, a multidimensional binary sorting method for rectangular boxes, used for quick range searching JO - The Visual Computer SP - 236 EP - 249 VL - 3 IS - 4 AB - In many geometrical applications data needs 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 areN boxes in an-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 theN boxes, which allows us to perform quick range queries (“box searches”) with respect to these boxes. When the givenN boxes are sufficiently scattered around then-dimensional space, the box search for an arbitrary query box of the same order of size as the sorted boxes can be carried out inO(logN) time. The necessary memory requirement for Box Sort is invariablyO(N). SN - 1432-2315 UR - https://doi.org/10.1007/BF01952830 DO - 10.1007/BF01952830 ID - Houthuys1987 ER -