Abstract:
For a univariate polynomial with real coefficients, a bound on its positiveness is a positive real number B such that the polynomial is non-negative at
every value larger than B. One of the best known bounds in literature is due
to Hoon Hong. Due to an algorithm of Koprowski-Mehlhorn-Ray, Hong’s
bound is linear time computable in the degree of the polynomial. In 2015,
Collins showed that an old bound due to Lagrange can be used to improve
upon Hong’s bound. Does this improvement over Hong’s bound come at
an extra computational cost? We show that Collins’ bound does not admit
a linear time algorithm like Hong’s bound. Our result shows that Hong’s
bound achieves a near optimal tradeoff between quality and computational
complexity. The problem of proving upper bounds on positiveness generalizes naturally for multivariate polynomials. We say that a positive real
number B is an upper bound on the positiveness of a multivariate polynomial
F(x1, x2,..., xn) ∈ R[x1,..., xn] if F(x1, x2,..., xn) ≥ 0, for all xi ≥ B. Here,
we improve upon the best known bound due to Hong. Our improvement is
achieved by generalizing a known bound for univariate complex polynomials
due to Westerfield. We also give an algorithm to compute a specific version
of Westerfield’s bound and the running time of our algorithm matches the
running time of the algorithm to compute Hong’s bound.
In the second part, we strengthen a known lower bound on orthogonal
range querying due to Fredman. Informally, Fredman’s lower bound says that
for orthogonal range querying, either the storage space has to be large or the
output complexity has to be large. We tighten this trade off by showing that
both storage space and the output complexity has to be large for orthogonal
range querying.
