  Space-filling curves (SFC, also known as FASS-curves) are a useful tool in
scientific computing and other areas of computer science to sequentialize
multidimensional grids in a cache-efficient and parallelization-friendly way
for storage in an array. Many algorithms, for example grid-based numerical PDE
solvers, have to access all neighbor cells of each grid cell during a grid
traversal. While the array indices of neighbors can be stored in a cell, they
still have to be computed for initialization or when the grid is adaptively
refined. A fast neighbor-finding algorithm can thus significantly improve the
runtime of computations on multidimensional grids.
  In this thesis, we show how neighbors on many regular grids ordered by
space-filling curves can be found in an average-case time complexity of $O(1)$.
In general, this assumes that the local orientation (i.e. a variable of a
describing grammar) of the SFC inside the grid cell is known in advance, which
can be efficiently realized during traversals. Supported SFCs include Hilbert,
Peano and Sierpinski curves in arbitrary dimensions. We assume that integer
arithmetic operations can be performed in $O(1)$, i.e. independent of the size
of the integer. We do not deal with the case of adaptively refined grids here.
However, it appears that a generalization of the algorithm to suitable adaptive
grids is possible. To formulate the neighbor-finding algorithm and prove its
correctness and runtime properties, a modeling framework is introduced. This
framework extends the idea of vertex-labeling to a description using grammars
and matrices. With the sfcpp library, we provide a C++ implementation to render
SFCs generated by such models and automatically compute all lookup tables
needed for the neighbor-finding algorithm. Furthermore, optimized
neighbor-finding implementations for various SFCs are included for which we
provide runtime measurements.
