Polynomial Root-Finding Methods Whose Basins of Attraction Approximate Voronoi Diagram.

Given a complex polynomial p( z) with at least three distinct roots, we first prove that no rational iteration function exists where the basin of attraction of a root coincides with its Voronoi cell. In spite of this negative result, we prove that the Voronoi diagram of the roots can be well approximated through a high order sequence of iteration functions, the Basic Family, B( z), m≥2. Let θ be a simple root of p( z), V( θ) its Voronoi cell, and A( θ) its basin of attraction with respect to B( z). We prove that given any closed subset C of V( θ), including any homothetic copy of V( θ), there exists m such that for all m≥ m, C is also a subset of A( θ). This implies that when all roots of p( z) are simple, the basins of attraction of B( z) uniformly approximate the Voronoi diagram of the roots to within any prescribed tolerance. Equivalently, the Julia set of B( z), and hence the chaotic behavior of its iterations, will uniformly lie to within prescribed strip neighborhood of the boundary of the Voronoi diagram. In a sense, this is the strongest property a rational iteration function can exhibit for polynomials. Next, we use the results to define and prove an infinite layering within each Voronoi cell of a given set of points, whether known implicitly as roots of a polynomial equation, or explicitly via their coordinates. We discuss potential application of our layering in computational geometry. [ABSTRACT FROM AUTHOR]