6/19/2023 0 Comments Geometry math solverGroebner basis completion is (depending on what you consider the exact problem) PSPACE-complete, so mostly likely exponential (in the number of variables).Īs to Tarski's result that elementary plane geometry is decidable, yes, that is a classic result (from the 50's). Anyway, the details of the algorithm make it a decision procedure (will stop with an answer of 'yes' or 'no').Īs a practical matter, you probably don't want to do this by hand. In some sense you could do this by hand for some very small trivial problems (It allows you to find the intersection of a given circle and line for example). Otherwise (and this is the beauty of it), the theorem -does- hold. If it eliminates so much to the point where it has an equation $0=1$, then you know you have a contradiction, and then your equations have no way of being satisfied, so the polynomials that describe the theorem are inconsistent, so the theorem itself does not hold. So the algorithm tries to 'reduce' as much as possible (eliminating leading terms where it can). The algorithm assumes an order on these terms, and then follows an analog of the numerical GCD algorithm (coincidentally or not in Euclid). It makes it easier if you multiply out everything so your equations are all of the form 'a sum of terms' = 0, where a term is a coefficient with a number of variables (possible none) multiplied, e.g. In analogy with eliminating columns in a matrix, you try to eliminate 'maximal' terms one by one. Essentially, it does just what you'd expect (but didn't realize you could) on higher degree multivariate polynomials. Groebner basis completion (via Buchberger's algorithm from the mid 70's) is what you can use. But with circles, you can have arbitrary degree. Then all you'd need is Gaussian elimination. And all you need is a procedure to find if there is a solution (some set of satisfying numbers or really a nontrivial set of equations) for them. So now you have a set of polynomial equations in many variables. Frankly, I'm not sure how to do angles, but my memory tells me that it is possible to 'deal' with them.Just by stating two points, you have a line. a line is defined by, well, two points.If you want a point on that circle, you instantiate this equation with the appropriate $x$ and $y$. Any possible distinct point should be named by some other pair $(x_2,y_2)$ (a proof that these two points coincide would show that $x_1=x_2$ and $y_1=y_2$). An undefined point is given two variables, an $x$ and $y$ coordinate $(x_1,y_1)$.Of the philosophical controversies discussed by the Greeks that inspired Euclid to set up his axioms, common notions and definitions (like what an angle is, what really is the action of a 'compass'), most of them are de facto resolved by how operations and variables work in real 2D analytic geometry with the Pythagorean theorem (which has been proven to be proof-power equivalent to Euclid's fifth postulate). There is a method to decide (true or not) any theorem in Euclid's Elements, by translating it into analytic geometry, or multivariate polynomials over the reals.
0 Comments
Leave a Reply. |