Convexity recognition of the union of polyhedra

In this paper we consider the following basic problem in polyhedral computa tion: Given two polyhedra in R-d, P and e, decide whether their union is co nvex, and, if so, compute it. We consider the three natural specializations of the problem: (1) when the polyhedra are given by halfspaces (H-polyhedr a), (2) when they are given by vertices and extreme rays (V-polyhedra), and (3) when both H- and V-polyhedral representations are available. Both the bounded (polytopes) and the unbounded case are considered. We show that the first two problems are polynomially solvable, and that the third problem i s strongly-polynomially solvable. (C) 2001 Elsevier Science B.V. All rights reserved.