Document - Deciding membership in a class of polyhedra

2012

Conference article Restricted

Deciding membership in a class of polyhedra

Ruggieri S.

Entailment Parameterized linear constraint Quantified linear implication

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.

Source: 20th European Conference on Artificial Intelligence, pp. 702–707, Montpellier, Francia, 27-31 agosto 2012

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:276192,
	title = {Deciding membership in a class of polyhedra},
	author = {Ruggieri S.},
	doi = {10.3233/978-1-61499-098-7-702},
	booktitle = {20th European Conference on Artificial Intelligence, pp. 702–707, Montpellier, Francia, 27-31 agosto 2012},
	year = {2012}
}