Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 Ek 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 141 times.
    This article's PDF has been downloaded 55 times.