Automatically Building Diagrams for Olympiad Geometry Problems
Authors:
Open Access
- 5 July 2021
- book chapter
- Published by Springer Nature
- p. 577-588
Abstract
We present a method for automatically building diagrams for olympiad-level geometry problems and implement our approach in a new open-source software tool, the Geometry Model Builder (GMB). Central to our method is a new domain-specific language, the Geometry Model-Building Language (GMBL), for specifying geometry problems along with additional metadata useful for building diagrams. A GMBL program specifies (1) how to parameterize geometric objects (or sets of geometric objects) and initialize these parameterized quantities, (2) which quantities to compute directly from other quantities, and (3) additional constraints to accumulate into a (differentiable) loss function. A GMBL program induces a (usually) tractable numerical optimization problem whose solutions correspond to diagrams of the original problem statement, and that we can solve reliably using gradient descent. Of the 39 geometry problems since 2000 appearing in the International Mathematical Olympiad, 36 can be expressed in our logic and our system can produce diagrams for 94% of them on average. To the best of our knowledge, our method is the first in automated geometry diagram construction to generate models for such complex problems.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Automatically Proving Plane Geometry Theorems Stated by Text and DiagramInternational Journal of Pattern Recognition and Artificial Intelligence, 2019
- Solving Geometry Problems Using a Combination of Symbolic and Numerical Reasoning2013
- Synthesizing geometry constructionsACM SIGPLAN Notices, 2011
- Geometric Constraint Solving in Parametric Computer-Aided DesignJournal of Computing and Information Science in Engineering, 2011
- GCLC — A Tool for Constructive Euclidean Geometry and More Than That2006
- Visualizing Geometrical Statements with GeoViewElectronic Notes in Theoretical Computer Science, 2004
- MMP/Geometer – A Software Package for Automated Geometric ReasoningLecture Notes in Computer Science, 2004
- Solution Selectors: A User-Oriented Answer to the Multiple Solution Problem in Constraint SolvingJournal of Mechanical Design, 2003
- Parametric Modeling2002
- An incremental constraint solverCommunications of the ACM, 1990