Computational complexity of diagram satisfaction in Euclidean geometry

Abstract: In this paper, it is shown that the problem of deciding whether or not a geometric diagram in Euclidean Geometry is satisfiable is NP-hard and in PSPACE, and in fact has the same complexity as the satisfaction problem for a fragment of the existential theory of the real numbers. The related problem of finding all of the possible (satisfiable) diagrams that can result when a segment of a diagram is extended is also shown to be NP-hard. [Copyright &y& Elsevier]