Deciding Membership in a Class of Polyhedra

Parameterized linear systems allow for modelling and reasoning over classes of polyhedra. Collections of squares, rectangles, polytopes, and so on can readily be defined by means of linear systems with parameters in constant terms. In this paper, we consider the membership problem of deciding whether a given polyhedron belongs to the class defined by a parameterized linear system. As an example, we are interested in questions such as: “does a given polytope belong to the class of hypercubes?” We show that the membership problem is NP-complete, even when restricting to the 2-dimensional plane. Despite the negative result, the constructive proof allows us to devise a concise decision procedure using constraint logic programming over the reals, namely CLP(R), which searches for a characterization of all instances of a parameterized system that are equivalent to a given polyhedron