Faster algorithms for computing Hong's bound on absolute positiveness (Q972846): Difference between revisions

Hong's bound is a bound on the absolute definitiveness of a real polynomial \(f\) in \(d\) variables. It gives a bound on the region where \(f\) and all its derivatives are positive. Let \(n\) be the number of monomials of \(f\). The obvious way of computing Hong's bound has time complexity \(O(dn^2)\); in this paper the authors improve this to \(O(n\log^d n)\). This result is achieved by representing the computation as the determination of the \textit{lower hull} of a set of points: the lower part of the convex hull. In the univariate case, \(d=1\), they even achieve an optimal result, time \(O(n)\), by mixing the computation of lower hulls with Hong's formula. As application an improvement in the continued fraction method of root isolation is mentioned. Correction text: We show that a linear-time algorithm for computing Hong's bound for positive roots of a univariate polynomial, described by the second and the third author in an article [ibid. 45, No. 6, 677-683 (2010; Zbl 1206.11151)], is incorrect. We present a corrected version.