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

Research output: Contribution to journalArticle

12 Citations (Scopus)

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
StatePublished - Jul 1 2011

Fingerprint

Polynomial Roots
Root-finding
Basin of Attraction
Voronoi Diagram
Rational functions
Polynomials
Roots
Iteration Function
Voronoi Cell
Computational geometry
Rational function
Root of a polynomial
Complex Polynomials
Subset
Julia set
Computational Geometry
Polynomial equation
Chaotic Behavior
Set of points
Strip

All Science Journal Classification (ASJC) codes

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

Cite this

@article{ce0ea1077f0f49ad8cb47716fbc3a4a8,
title = "Polynomial Root-Finding Methods Whose Basins of Attraction Approximate Voronoi Diagram",
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.",
author = "Bahman Kalantari",
year = "2011",
month = "7",
day = "1",
doi = "10.1007/s00454-011-9330-3",
language = "English (US)",
volume = "46",
pages = "187--203",
journal = "Discrete and Computational Geometry",
issn = "0179-5376",
publisher = "Springer New York",
number = "1",

}

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

In: Discrete and Computational Geometry, Vol. 46, No. 1, 01.07.2011, p. 187-203.

Research output: Contribution to journalArticle

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.

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

VL - 46

SP - 187

EP - 203

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 1

ER -