| Language |
English
|
| From |
2010/07/02 15:00
|
| To |
2010/07/02 16:30
|
| Place | Room 110, RIMS, Kyoto University |
| Seminar Name | GCOE Semiar |
| Title |
Polynomial Root-Finding Methods Whose Basins of Attraction Approximate Voronoi Diagram |
| Field |
Analysis
|
| Speakers | Bahman Kalantari |
| Affiliation | Department Of Computer Science, Rutgers University |
| Abstract | Given a complex polynomial ) with at least three distinct roots, we first prove 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 the Voronoi diagram of the roots can be well approximated through a high order sequence of iteration functions, the Basic Family, , m \ge 2) . Let  be a simple root of , V (\theta)) its Voronoi cell, and ) its basin of attraction with respect to ) . We prove that given any closed subset  of ) , including any homothetic copy of , there exists  such that for all  , is also a subset of ) . This implies when all roots of are simple, the basins of attraction of uniformly approximates the Voronoi diagram of the roots to within any prescribed tolerance. Equivalently, the Julia set of , and hence the chaotic behavior of its iterations, will uniformly lie to within prescribed strip neighborhood of the boundary of Voronoi diagram. In a sense this is the strongest property a rational iteration function can exhibit for polynomials. Next, we use the results to de ne and prove an in nite 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.
Key words. Complex polynomials; Voronoi diagrams; zeros; Newton's method; iteration functions; fractal; Julia set, dynamical systems; computational geometry |
|