DIRECTIONAL CONVEXITY RECOGNITION OF THE UNION OF SEVERAL POLYHEDRA

Abstract

The article is devoted to the algorithmic aspects of partial convexity, which is a generalization of the classical concept of convexity. Often, it is necessary to introduce the concept of partial convexity when studying many applied problems such as problems of VLSI design, image processing, database design, etc., since the requirement of traditional convexity is too restrictive for such problems. At the same time, the partial convexity preserves many useful properties of classical convexity, which makes it possible to find effective algorithms for solving these problems. A problem for recognizing directional convexity of the union of polyhedral sets in the n-dimensional linear space is investigated. We have established a necessary and sufficient attribute of the partial convexity for the union of polyhedral sets. Using this attribute of partial convexity, in the case of the finiteness of the set of directions of partial convexity, we have developed a polynomial recognition algorithm for the union of several polyhedral sets given by intersections of half-spaces, provided that the number of these sets is fixed. We note that earlier for the problem under consideration, a polynomial algorithm for solving it was known only for the case of the union of two polyhedral sets.