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

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

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, Bm(z), m≥2. Let θ be a simple root of p(z), V(θ) its Voronoi cell, and Am(θ) its basin of attraction with respect to Bm(z). We prove that given any closed subset C of V(θ), including any homothetic copy of V(θ), there exists m0 such that for all m≥m0, C is also a subset of Am(θ). This implies that when all roots of p(z) are simple, the basins of attraction of Bm(z) uniformly approximate the Voronoi diagram of the roots to within any prescribed tolerance. Equivalently, the Julia set of Bm(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.

Original languageEnglish (US)
Pages (from-to)187-203
Number of pages17
JournalDiscrete and Computational Geometry
Volume46
Issue number1
DOIs
Publication statusPublished - Jul 1 2011

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Complex polynomials
  • Computational geometry
  • Dynamical systems
  • Fractal
  • Iteration functions
  • Julia set
  • Newton's method
  • Voronoi diagram
  • Zeros

Cite this