Neighborhood Sequences on nD Hexagonal/Face-Centered-Cubic Grids

摘要

The two-dimensional hexagonal grid and the three-dimensional face-centered cubic grid can be described by intersecting Z~3 and Z~4 with a (hyper)plane. Corresponding grids in higher dimensions (nD) are examined. In this paper, we define distance functions based on neighborhood sequences on these, higher dimensional generalizations of the hexagonal grid. An algorithm to produce a shortest path based on neighborhood sequences between any two gridpoints is presented. A formula to compute distance and condition of metricity are presented for neighborhood sequences using two types of neighbors. Distance transform as an application of these distances is also shown.