Generalized Directions on a Compass

Abstract

Beside the four cardinal directions on a compass (North, East, South,
West), there are more fine grained directions between them, such as
NorthEast and EastNorthEast. They are formed by concatenating neighboring
directions, but not arbitrarily: EastNorth and NorthEastEast are incorrect
directions. We study the underlying (though not explicitly given)
recursive naming procedure. As it turns out, these generalized directions on
a compass are indeed unique and are formed by a tabled Lindenmayer system,
usually used to describe cellular plant growth. As we show, deciding
whether a given string actually forms a direction is solvable in linear time.