Space-filling curves and their use in the design of geometric data structures

AbstractWe are given a two-dimensional square grid of size N × N, where N :=2n and n⩾0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c + 1 to c + N2, for some c⩾0. We call a SFC recursive (RSFC) if it can be recursively divided into four square RSFCs of equal size.We prove several useful and interesting combinatorial properties of recursive and general SFCs. For an optimality criterion that is important in the design of geometric data structures, we propose a RSFC that is optimal in the worst case and outperforms the previously known RSFCs