## Propagation function: towards constant time algorithms

#### Abstract

Let *P** _{n}* be the regular

*n*-sided polygon inscribed in a circle of radius 1 in the plane. The distance from

*x*to

*y*induced by

*P*

*is the smallest size of the homothety of*

_{n}*P*

*centered at*

_{n}*x*and containing

*y.*On

*X,*simply connected planar set, the propagation functionis defined by

*(x)*= sup

*∈*

_{y}

_{X}*(x,y)*where

*(x,y)*is the geodesic distance in

*X,*that is the lower bound of the length (induced by

*P*

*) of the paths entirely lying inside*

_{n}*X*and linking

*x*to

*y.*Efficient algorithms forare 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) =*sup

*∈*

_{y}

_{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.*

#### To cite this article

*Acta Stereologica*[En ligne], Volume 13 (1994), Number 1 - Proceedings of the sixth European congress for stereology - Part two - May 1994, 137-142 URL : https://popups.ulg.ac.be/0351-580x/index.php?id=4558.