Propagation function: towards constant time algorithms
Abstract
Let Pn be the regular n-sided polygon inscribed in a circle of radius 1 in the plane. The distance from x to y induced by Pn is the smallest size of the homothety of Pn centered at x and containing y. On X, simply connected planar set, the propagation function
is defined by
(x) = supy∈X
(x,y) where
(x,y) is the geodesic distance in X, that is the lower bound of the length (induced by Pn) of the paths entirely lying inside X and linking x to y. Efficient algorithms for
are based on the following remark: the farthest points to any x in X may have only a few possible locations Y. In this paper, it is shown that, as in the convex case, there exists a set Y with at most n elements, such that
(x) = supy∈Y
(x,y). In the case of the square lattice equipped with the 4-connectivity distance, this theorem leads to an algorithm computing the propagation function by means of at most 7 geodesic balls, whatever the shape of X.