Geometric containment, common roots of polynomials and partial orders
The reduction to vector dominance of two unrelated problems is studied; the two problems are1.Geometric containment: given a class of geometric figures, determine for any two figures in the class whether one is contained in the other (perhaps after translation, rotation and even reflection).2.Common roots of polynomials: given a class of polynomials, determine for any two polynomials in the class whether they have positive common roots. A general characterization of the relationship between geometric containment and properties of finite parametrizations of geometric figures is given in the form of an abstract theorem on partial orders. It is shown that the existing impossibility result for rectangles can be formulated as an instance of the abstract result. The abstract result is then applied to some other classes of figures, and several instances are given using a known low-dimensional negative result to obtain a new higher-dimensional one. The abstract theorem is then used to prove that domination of polynomials is not reducible to vector dominance even for the restricted class of quadratic polynomials.
|Series||Lecture Notes in Computer Science|
Santoro, N, Sidney, J.B. (J. B.), Sidney, S.J. (S. J.), & Urrutia, J. (J.). (1988). Geometric containment, common roots of polynomials and partial orders. In Lecture Notes in Computer Science. doi:10.1007/BFb0035853