A complete and practical algorithm for geometric theorem proving (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A complete and practical algorithm for geometric theorem proving (extended abstract)

Full text

Pdf (1.09 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the eleventh annual symposium on Computational geometry table of contents

Vancouver, British Columbia, Canada

Pages: 277 - 286

Year of Publication: 1995

ISBN:0-89791-724-3

Author

Ashutosh Rege

Computer Science Division, University of California, Berkeley, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 10, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/220279.220309 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	John F. Canny, Computing Roadmaps of General Semi-Algebraic Sets, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.94-107, October 07-11, 1991
	2	John F. Canny, An Improved Sign Determination Algorithm, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.108-117, October 07-11, 1991
	3	S.-C. Chou. Proving elementary geometry theorems using Wu's algorithm. In W.W. Bledsoe and D.W. Loveland, editors, Theorem Proving: After 25 Years. American Mathematical Society, 1984.
	4	S.-C. Chou, Mechanical geometry theorem proving, Kluwer Academic Publishers, Norwell, MA, 1987
	5	J. Little D. Cox and D. O'Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1992.
	6	G. Gallo and B. Mishra. Efficient algorithms and bounds for Wu-Ritt characteristic sets. In T. Mora and C. Traverso, editors, Effective Methods in Algebraic Geometry, volume 94 of Progress in Mathematics, pages 119-142. Birkh~iuser, 1991.
	7	H. Gelernter, Realization of a geometry-theorem proving machine, Computers & thought, MIT Press, Cambridge, MA, 1995
	8	Deepak Kapur, Geometry theorem proving using Hilbert's Nullstellensatz, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.202-208, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32479]
	9	D. Kapur, A refutational approach to geometry theorem proving, Geometric reasoning, MIT Press, Cambridge, MA, 1989
	10	B. Kutzler , S. Stifter, On the application of Buchberger's algorithm to automated geometry theorem proving, Journal of Symbolic Computation, v.2 n.4, p.389-397, Dec. 1986 [doi>10.1016/S0747-7171(86)80006-2]
	11	A. Rege. A complete and practical algorithm for geometric theorem proving. Manuscript for journal submission and Tech Report (UC Berkeley), 1995.
	12	A. Rege and j. Canny. Straight-line programs for real field extensions and perturbations. To be submitted to special issue of International journal of Computational Geometry and Applications, 1995.
	13	A. Rege and J. Canny. A toolkit for algebra and geometry. Submitted to the International Symposium on Symbolic and Algebraic Computation, Montreal, 1995.
	14	J. Renegar. On the computational complexity and geometry of the first-order theory of the reals, parts I, II and III. Technical Report 852,855,856, Cornell University, Operations Research Dept., 1989.
	15	J.F. Ritt. Differential Equations from the Algebraic Standpoint. Number 14 in AMS Colloquium publications. American Mathematical Society, New York, 1932.
	16	J.F. Ritt. Differential Algebra. Number 33 in AMS Colloquium publications. American Mathematical Society, New York, 1950.
	17	W. Wu. On the decision problem and mechanization of theorem proving in elementary geometry. Sci. Sir~ica, 21:150-172, 1978.
	18	W. Wu. Some recent advances in mechanical theorem proving of geometries. In W.W. Bledsoe and D.W. Loveland, editors, Theorem Proving: After 25 Years. American Mathematical Society, 1984.
	19	R. Zippel. Effective Polynomial Computation. Kluwer Academic publishers, Massachusetts, 1993.

CITED BY 4

	Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Computing exact geometric predicates using modular arithmetic with single precision, Proceedings of the thirteenth annual symposium on Computational geometry, p.174-182, June 04-06, 1997, Nice, France
	Aaron Wallack , Ioannis Z. Emiris , Dinesh Manocha, MARS: a MAPLE/MATLAB/C resultant-based solver, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.244-251, August 13-15, 1998, Rostock, Germany
	Sebti Foufou , Dominique Michelucci , Jean-Paul Jurzak, Numerical decomposition of geometric constraints, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.143-151, June 13-15, 2005, Cambridge, Massachusetts
	S. Petitjean, Algebraic Geometry and Computer Vision: Polynomial Systems, Real andComplex Roots, Journal of Mathematical Imaging and Vision, v.10 n.3, p.191-220, May 1999