The use of linear quadtrees in a numerical problem. (English) Zbl 0532.65007

Gargantini, Irene

SIAM J. Numer. Anal. 20, 1161-1169 (1983).

Linear quadtrees have proved to be a useful structure for representing quadrants’ subdivisions and groupings in association with the encoding of two-dimensional binary images. In this paper it is shown that linear quadtrees can also be successfully applied to the memory management of the class of polynomial solvers proposed by P. Henrici [Applied and computational complex analysis. Vol. 1: Power series, integration, conformal mapping, location of zeros. (1974; Zbl 0313.30001)] and by P. Henrici and the author [Constructive Aspects Fundam. Theor. Algebra, Proc. Sympos. Zürich-Ruschlikon 1967, 77-113 (1969; Zbl 0194.469)]. The problem of evaluating ”the bounding box” of a connected region, given as a linear quadtree, is also considered, and an algorithmic solution presented.

MSC:

65D15	Algorithms for approximation of functions
68T10	Pattern recognition, speech recognition
65H05	Numerical computation of solutions to single equations

Keywords:

linear quadtrees; quadrants’ subdivisions and groupings; two-dimensional binary images; polynomial solvers; polynomial zero-finder; pattern recognition