Timeline for Algorithm for checking existance of real roots for Polynomials in more than one variable
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2011 at 12:43 | comment | added | ostap bender | Yes, there are indeed more efficient Algorithms. As far as I know all of them use numerical approximation (in higher dimensions) either to calculate roots or to calculate a minimum / maximum. So I was curious whether there is an exact Algorithm, having a runtime bounded by the dimension (ideally with polynomial complexity). As far as I understood the Discussion at mathoverflow.net/questions/43979/… , there is no such algorithm yet (at least not for the more general case of counting roots of fewnomials) | |
| Dec 15, 2011 at 15:17 | comment | added | Andreas Blass | I would expect that, for the specific problem of checking whether two ellipsoids overlap, there are more efficient algorithms than the relevant special case of Tarski's general algorithm. Unfortunately, this is far from my expertise, so I don't actually know any such algorithms. For conceptual purposes (if not for algorithmic ones), it might help to arrange, by an affine transformation, that one of your two ellipsoids is the unit ball. | |
| Dec 15, 2011 at 14:28 | vote | accept | ostap bender | ||
| Dec 15, 2011 at 14:27 | comment | added | ostap bender | Thank you. My Question was motivated by developing Collision avoidance Strategies. I am interested in an algorithm Checking whether two (possibly n-dimensional) Ellipsoids overlap. Using a polynomial Representation of ellipsoids one could check if at least one real valued solution exist in order to prove a collision. For a proper performance Comparison with other algorithms (which might be based on numeric methods) I was interested in how computational complexity behaves, when the dimension of the problem grows. | |
| Dec 15, 2011 at 13:47 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 45 characters in body
|
| Dec 15, 2011 at 13:40 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |