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 languageEnglish (US)
Title of host publication6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009
Pages31-40
Number of pages10
DOIs
StatePublished - Dec 1 2009
Event6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 - Copenhagen, Denmark
Duration: Jun 23 2009Jun 26 2009

Publication series

Name6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

Other

Other6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009
CountryDenmark
CityCopenhagen
Period6/23/096/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

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.",
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

Voronoi diagrams and polynomial root-finding. / Kalantari, Bahman.

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.

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

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