  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.
