Premium
Propagation function: constant time algorithms
Author(s) -
SCHMITT M.
Publication year - 1995
Publication title -
journal of microscopy
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.569
H-Index - 111
eISSN - 1365-2818
pISSN - 0022-2720
DOI - 10.1111/j.1365-2818.1995.tb03605.x
Subject(s) - geodesic , constant (computer programming) , polygon (computer graphics) , regular polygon , algorithm , function (biology) , planar , mathematics , constant function , point (geometry) , combinatorics , plane (geometry) , computer science , geometry , mathematical analysis , telecommunications , computer graphics (images) , frame (networking) , evolutionary biology , piecewise , biology , programming language
SUMMARY This paper deals with constant time algorithms computing the propagation function of X , assumed to be a simply connected planar set. This function, extensively used for object measurements and shape characterization, is defined as the geodesic distance to the furthest point in X , where the geodesic distance between two points in X is the lower bound of the length of paths entirely lying inside X and linking the two points. When the plane is equipped with a distance derived from a regular n ‐sided polygon (distances on image lattices), efficient algorithms for the propagation function are based on the following remark: the furthest points to any point 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, giving rise to constant time algorithms. Algorithms designed to compute this set Y and an implementation for the square lattice equipped with the four‐connectivity distance, by means of at most seven geodesic balls, whatever the shape of X , are described.