Automation of Triangle Ruler-and-Compass Constructions Using Constraint Solvers
This provides an efficient, low-effort solution for automating geometric constructions in computational geometry, though it is incremental as it applies existing constraint-solving methods to a known domain.
The paper tackles the problem of automating triangle ruler-and-compass constructions by using finite-domain constraint solvers, achieving comparable performance to dedicated tools on 74 problems from Wernick's list while often finding shorter constructions.
In this paper, we present an approach to automated solving of triangle ruler-and-compass construction problems using finite-domain constraint solvers. The constraint model is described in the MiniZinc modeling language, and is based on the automated planning. The main benefit of using general constraint solvers for such purpose, instead of developing dedicated tools, is that we can rely on the efficient search that is already implemented within the solver, enabling us to focus on geometric aspects of the problem. We may also use the solver's built-in optimization capabilities to search for the shortest possible constructions. We evaluate our approach on 74 solvable problems from the Wernick's list, and compare it to the dedicated triangle construction solver ArgoTriCS. The results show that our approach is comparable to dedicated tools, while it requires much less effort to implement. Also, our model often finds shorter constructions, thanks to the optimization capabilities offered by the constraint solvers.