View article

In this paper, we provide a formal definition of Sense of Direction. In particular, we define the properties whose presence in a labeling make possible the reduction in communication complexity uncovered by the previous investigations. This is achieved by identifying the mechanisms which operate in the reduction, and determining the conditions for the existence of those mechanisms. Based on the formal definition, we have identified and defined four general classes of labelings and analyzed their properties. These classes include all the labelings used in the literature.