On polynomials associated to Voronoi diagrams of point sets and crossing numbers

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_{l e q 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.

This page was built for publication: On polynomials associated to Voronoi diagrams of point sets and crossing numbers