Distances defined by neighborhood sequences (Q1082093)

In this paper the general properties of distance functions over digitized space are discussed. It is assumed that a distance between two points is defined as the length of the shortest path connecting them in the underlying graph which is defined by a given neighborhood sequence. A necessary and sufficient condition for a neighborhood sequence to define a distance function is derived. The problem of how tight such distances can approximate the Euclid distance is also discussed.