セミナー

発表言語 英語
開催日 2010年07月02日 15時00分
終了日 2010年07月02日 16時30分
開催場所京都大学数理解析研究所110号室
セミナー名GCOE特別講義
タイトル Polynomial Root-Finding 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