Distances defined by neighborhood sequences

This paper investigates general properties of distance functions defined over digitized space. We assume that a distance between two points is defined as the length of a shortest path connecting them in the underlying graph which is defined by a given neighborhood sequence. Many typical distance functions can be described in this form, but there are cases in which given neighborhood sequence do not define distance functions. We first derive a necessary and sufficient condition for a neighborhood sequence to define a distance function. We then discuss another important problem of estimating how tight such distances can approximate the Euclid distance from the view point of relative error and absolute error.