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

Pages (from-to) | 187-203 |

Number of pages | 17 |

Journal | Discrete and Computational Geometry |

Volume | 46 |

Issue number | 1 |

DOIs | |

State | Published - 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

}

**Polynomial Root-Finding Methods Whose Basins of Attraction Approximate Voronoi Diagram.** / Kalantari, Bahman.

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Kalantari, Bahman

PY - 2011/7/1

Y1 - 2011/7/1

N2 - 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.

AB - 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.

KW - Complex polynomials

KW - Computational geometry

KW - Dynamical systems

KW - Fractal

KW - Iteration functions

KW - Julia set

KW - Newton's method

KW - Voronoi diagram

KW - Zeros

UR - http://www.scopus.com/inward/record.url?scp=79955600629&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955600629&partnerID=8YFLogxK

U2 - 10.1007/s00454-011-9330-3

DO - 10.1007/s00454-011-9330-3

M3 - Article

AN - SCOPUS:79955600629

VL - 46

SP - 187

EP - 203

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 1

ER -