発表言語 
英語

開催日 
2010年07月02日 15時00分

終了日 
2010年07月02日 16時30分

開催場所  京都大学数理解析研究所110号室 
セミナー名  GCOE特別講義 
タイトル 
Polynomial RootFinding Methods Whose Basins of Attraction Approximate Voronoi Diagram 
分野 
解析

講演者名  Bahman Kalantari 
講演者所属  Department Of Computer Science, Rutgers University 
概要  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, . Let be a simple root of 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 
