Geodesic
On polynomials associated to Voronoi diagrams of point sets and crossing numbers
Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 2.

Voir la notice de l'article provenant de la source Episciences

Three polynomials are defined for given sets $S$ of $n$ points in general position in the plane: The Voronoi polynomial with coefficients the numbers of vertices of the order-$k$ Voronoi diagrams of $S$, the circle polynomial with coefficients the numbers of circles through three points of $S$ enclosing $k$ points of $S$, and the $E_{\leq k}$ polynomial with coefficients the numbers of (at most $k$)-edges of $S$. We present several formulas for the rectilinear crossing number of $S$ in terms of these polynomials and their roots. We also prove that the roots of the Voronoi polynomial lie on the unit circle if, and only if, $S$ is in convex position. Further, we present bounds on the location of the roots of these polynomials. 
@article{DMTCS_2024_26_2_a13,
     author = {Claverol, Merc\`e and Heras-Parrilla, Andrea de las and Flores-Pe\~naloza, David and Huemer, Clemens and Orden, David},
     title = {On polynomials associated to {Voronoi} diagrams of point sets and crossing numbers},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2024},
     doi = {10.46298/dmtcs.12443},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12443/}
}
TY  - JOUR
AU  - Claverol, Mercè
AU  - Heras-Parrilla, Andrea de las
AU  - Flores-Peñaloza, David
AU  - Huemer, Clemens
AU  - Orden, David
TI  - On polynomials associated to Voronoi diagrams of point sets and crossing numbers
JO  - Discrete mathematics & theoretical computer science
PY  - 2024
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12443/
DO  - 10.46298/dmtcs.12443
LA  - en
ID  - DMTCS_2024_26_2_a13
ER  - 
%0 Journal Article
%A Claverol, Mercè
%A Heras-Parrilla, Andrea de las
%A Flores-Peñaloza, David
%A Huemer, Clemens
%A Orden, David
%T On polynomials associated to Voronoi diagrams of point sets and crossing numbers
%J Discrete mathematics & theoretical computer science
%D 2024
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12443/
%R 10.46298/dmtcs.12443
%G en
%F DMTCS_2024_26_2_a13
Claverol, Mercè; Heras-Parrilla, Andrea de las; Flores-Peñaloza, David; Huemer, Clemens; Orden, David. On polynomials associated to Voronoi diagrams of point sets and crossing numbers. Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 2. doi : 10.46298/dmtcs.12443. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12443/

Cité par Sources :