Mercè Claverol ; Andrea de las Heras-Parrilla ; David Flores-Peñaloza ; Clemens Huemer ; David Orden - On polynomials associated to Voronoi diagrams of point sets and crossing numbers

dmtcs:12443 - Discrete Mathematics & Theoretical Computer Science, November 4, 2024, vol. 26:2 - https://doi.org/10.46298/dmtcs.12443
On polynomials associated to Voronoi diagrams of point sets and crossing numbersArticle

Authors: Mercè Claverol ; Andrea de las Heras-Parrilla ; David Flores-Peñaloza ; Clemens Huemer ; David Orden

    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.


    Volume: vol. 26:2
    Section: Combinatorics
    Published on: November 4, 2024
    Accepted on: May 20, 2024
    Submitted on: October 19, 2023
    Keywords: Mathematics - Combinatorics,Computer Science - Computational Geometry,Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 44 times.
    This article's PDF has been downloaded 19 times.