# Efficiency Considerations

An important goal of our constraint solver is to achieve interactive speed. The system as developed has two components, a graphical user interface (GUI), and the constraint solver itself. These two components communicate with each other via the textual Erep solid modeling scheme. Figure 1 indicates the information flow of the system.

```
Figure 1: Architecture of the constraint solver system
```
The textual problem specification is handed to the constraint solver which translates the constraints into a graph, and, as described elsewhere, solves them by graph reductions. The solver capabilities are the consequence of certain construction steps that have been implemented. If a particular constraint problem can be solved using these steps, then our solver will find a solution. Where the construction steps involve ruler-and-compass constructions, only quadratic equations need to be solved. But some construction steps are permitted that are not ruler-and-compass, and in those situations the roots of a univariate polynomial are found numerically. This polynomial has been precomputed except for the coefficients which are functions of specific constraint values.

A well-constrained geometric problem can have exponentially many solutions in the number of constraints. This is because the solutions correspond to the algebraic set of a zero-dimensional ideal whose generating polynomials are nonlinear. Our solver can determine all possible solutions. But doing so every time would waste time and overwhelm the user. So, certain heuristics narrow down the solutions to a final configuration that corresponds to the intended solution with high probability. In case a different solution is wanted, the solver can be redirected to the intended solution interactively.