## 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 2011 |

## 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