Several approaches to proving theorems in Elementary Geometry using constructive methods have been proposed. Three general approaches can be distinguished: methods based on Groebner bases, the acclaimed Wu's Method and Cell decomposition.
Methods based on Groebner Basis are general but their worst case time complexity is double-exponential, while the complexity of Wu’s method is only single-exponential but it proves theorems in Complex Geometry (or geometry based on any algebraically closed field). Methods based on cell decomposition are general methods for Real Geometry but remain slow in practice.
While in Italy, I started exploring randomized approaches for proving geometric conjecture in Elementary Geometry in order to reduce the complexity. The idea is to prove the validity of a conjecture by testing it on randomly generating instances of its construction.
A randomized version of Wu’s prover, using Schwartz-Zippel Zero Test for multivariate polynomials, was explored but didn’t result to be successful because of the extremely large test set. Therefore, I pursued a different approach, symbolical-numerical, related in some way to
Hong’s “proving by example” method. This conducted me to another interesting problem: the generalization of Schwartz-Zippel Zero-Test to radical expressions (which has divisions and square-roots).
This approach, based on this novel zero-test, is the first method with polynomial time complexity and generalizes Wu’s method for proving theorems in Real Geometry. It is useful in practice to test many conjectures, and quickly reject false ones.
Chee Yap and Chen Li contributed in the last stage of this project; in particular, the system relies on their Core Library, for the exact precision. The prover is part of the Core Library and currently downloadable as its main application.
For details, D.Tulone, C.Yap, C.Li Randomized Zero Testing of Radical Expressions and Elementary Geometry Theorem Proving, in Proc. Int'l Workshop on Automated Deduction in Geometry (ADG'00). The full version can also be found in LNCS/LNAI 2061.