On Convexity of Right-Closed Integral Sets
E. Salimi *
Daniel J. Epstein Department Industrial Engineering, Viterbi School of Engineering, University of Southern California Los Angeles, CA 90089, USA.
R.S. Sreenivas
Industrial & Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA.
*Author to whom correspondence should be addressed.
Abstract
Let N denote the set of non-negative integers. A set of non-negative, n-dimensional integral vectors, M⊂Nn, is said to be right-closed, if ((x ∈ M) ∧ (y ≥ x) ∧ (y ∈Nn)) ⇒ (y ∈ M). In this paper, we present a polynomial time algorithm for testing the convexity of a right-closed set of integral vectors, when the dimension n is xed. Right-closed set of integral vectors are innitely large, by denition. We compute the convex-hull of an appropriately-dened nite subset of this innite-set of vectors. We then check if a stylized Linear Program has a non-zero optimal value for a special collection of facets of this convex-hull. This result is to be viewed against the backdrop of the fact that checking the convexity of a real-valued, geometric set can only be accomplished in an approximate sense; and, the fact that most algorithms involving sets of real-valued vectors do not apply directly to their integral counterparts. This observation plays an important role in the ecient synthesis of Supervisory Policies that avoid Livelocks in Discrete-Event/Discrete-State Systems.
Keywords: Convexity, right-closed sets, computational geometry