On polynomials associated to Voronoi diagrams of point sets and crossing numbers
Open Access
- 4 November 2024
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Discrete Mathematics & Theoretical Computer Science
- Vol. 26:2 (Combinator)
Abstract
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.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- The edge labeling of higher order Voronoi diagramsJournal of Global Optimization, 2024
- On circles enclosing many pointsDiscrete Mathematics, 2021
- The rectilinear local crossing number of KJournal of Combinatorial Theory, Series A, 2017
- The Rectilinear Crossing Number of K n : Closing in (or Are We?)2012
- Unimodularity of zeros of self-inversive polynomialsActa Mathematica Hungarica, 2012
- On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of K nDiscrete & Computational Geometry, 2012
- New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of KnDiscrete & Computational Geometry, 2007
- On the Polynomials with All Their Zeros on the Unit CircleJournal of Mathematical Analysis and Applications, 1995
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- The number of small semispaces of a finite set of points in the planeJournal of Combinatorial Theory, Series A, 1986