# Voronoi diagrams and polynomial root-finding

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

### Abstract

Voronoi diagram of points in the Euclidean plane and its computation is foundational to computational geometry. Polynomial root-finding is the origin of fundamental discoveries in all of mathematics and sciences. There is an intrinsic connection between polynomial root-finding in the complex plane and the approximation of Voronoi cells of its roots via a fundamental family of iteration functions, the Basic Family. For instance, the immediate basin of attraction of a root of a complex polynomial under Newton's method is a rough approximation to its Voronoi cell. We formally introduce these connections through the Basic Family of iteration functions, its properties with respect to Voronoi diagrams, and a corresponding visualization called polynomiography. Polynomiography is a medium for art, math, education and science. By making use of the Basic Family we introduce a layering of the points within each Voronoi cell of a polynomial root and study its properties and potential applications. In particular, we prove some novel results about the Basic Family in connection with Voronoi diagrams.

Original language English (US) 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 31-40 10 https://doi.org/10.1109/ISVD.2009.17 Published - Dec 1 2009 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 - Copenhagen, DenmarkDuration: Jun 23 2009 → Jun 26 2009

### Publication series

Name 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

### Other

Other 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 Denmark Copenhagen 6/23/09 → 6/26/09

### Fingerprint

Polynomial Roots
Root-finding
Voronoi Diagram
Voronoi Cell
Polynomials
Iteration Function
Computational geometry
Roots
Root of a polynomial
Newton-Raphson method
Complex Polynomials
Euclidean plane
Basin of Attraction
Computational Geometry
Approximation
Visualization
Newton Methods
Education
Argand diagram
Rough

### All Science Journal Classification (ASJC) codes

• Information Systems
• Biomedical Engineering
• Applied Mathematics

### Keywords

• Complex polynomials
• Dynamical systems
• Fractal
• Iteration functions
• Newton's method
• Voronoi diagrams
• Zeros

### Cite this

Kalantari, B. (2009). Voronoi diagrams and polynomial root-finding. In 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 (pp. 31-40). [5362425] (6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009). https://doi.org/10.1109/ISVD.2009.17
Kalantari, Bahman. / Voronoi diagrams and polynomial root-finding. 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009. 2009. pp. 31-40 (6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009).
@inproceedings{555576755ec44e8f908604801109f32a,
title = "Voronoi diagrams and polynomial root-finding",
abstract = "Voronoi diagram of points in the Euclidean plane and its computation is foundational to computational geometry. Polynomial root-finding is the origin of fundamental discoveries in all of mathematics and sciences. There is an intrinsic connection between polynomial root-finding in the complex plane and the approximation of Voronoi cells of its roots via a fundamental family of iteration functions, the Basic Family. For instance, the immediate basin of attraction of a root of a complex polynomial under Newton's method is a rough approximation to its Voronoi cell. We formally introduce these connections through the Basic Family of iteration functions, its properties with respect to Voronoi diagrams, and a corresponding visualization called polynomiography. Polynomiography is a medium for art, math, education and science. By making use of the Basic Family we introduce a layering of the points within each Voronoi cell of a polynomial root and study its properties and potential applications. In particular, we prove some novel results about the Basic Family in connection with Voronoi diagrams.",
keywords = "Complex polynomials, Dynamical systems, Fractal, Iteration functions, Newton's method, Voronoi diagrams, Zeros",
author = "Bahman Kalantari",
year = "2009",
month = "12",
day = "1",
doi = "10.1109/ISVD.2009.17",
language = "English (US)",
isbn = "9780769537818",
series = "6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009",
pages = "31--40",
booktitle = "6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009",

}

Kalantari, B 2009, Voronoi diagrams and polynomial root-finding. in 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009., 5362425, 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009, pp. 31-40, 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009, Copenhagen, Denmark, 6/23/09. https://doi.org/10.1109/ISVD.2009.17
6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009. 2009. p. 31-40 5362425 (6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Voronoi diagrams and polynomial root-finding

AU - Kalantari, Bahman

PY - 2009/12/1

Y1 - 2009/12/1

N2 - Voronoi diagram of points in the Euclidean plane and its computation is foundational to computational geometry. Polynomial root-finding is the origin of fundamental discoveries in all of mathematics and sciences. There is an intrinsic connection between polynomial root-finding in the complex plane and the approximation of Voronoi cells of its roots via a fundamental family of iteration functions, the Basic Family. For instance, the immediate basin of attraction of a root of a complex polynomial under Newton's method is a rough approximation to its Voronoi cell. We formally introduce these connections through the Basic Family of iteration functions, its properties with respect to Voronoi diagrams, and a corresponding visualization called polynomiography. Polynomiography is a medium for art, math, education and science. By making use of the Basic Family we introduce a layering of the points within each Voronoi cell of a polynomial root and study its properties and potential applications. In particular, we prove some novel results about the Basic Family in connection with Voronoi diagrams.

AB - Voronoi diagram of points in the Euclidean plane and its computation is foundational to computational geometry. Polynomial root-finding is the origin of fundamental discoveries in all of mathematics and sciences. There is an intrinsic connection between polynomial root-finding in the complex plane and the approximation of Voronoi cells of its roots via a fundamental family of iteration functions, the Basic Family. For instance, the immediate basin of attraction of a root of a complex polynomial under Newton's method is a rough approximation to its Voronoi cell. We formally introduce these connections through the Basic Family of iteration functions, its properties with respect to Voronoi diagrams, and a corresponding visualization called polynomiography. Polynomiography is a medium for art, math, education and science. By making use of the Basic Family we introduce a layering of the points within each Voronoi cell of a polynomial root and study its properties and potential applications. In particular, we prove some novel results about the Basic Family in connection with Voronoi diagrams.

KW - Complex polynomials

KW - Dynamical systems

KW - Fractal

KW - Iteration functions

KW - Newton's method

KW - Voronoi diagrams

KW - Zeros

UR - http://www.scopus.com/inward/record.url?scp=77951492777&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951492777&partnerID=8YFLogxK

U2 - 10.1109/ISVD.2009.17

DO - 10.1109/ISVD.2009.17

M3 - Conference contribution

AN - SCOPUS:77951492777

SN - 9780769537818

T3 - 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

SP - 31

EP - 40

BT - 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

ER -

Kalantari B. Voronoi diagrams and polynomial root-finding. In 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009. 2009. p. 31-40. 5362425. (6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009). https://doi.org/10.1109/ISVD.2009.17