
CS Seminar: Fabio Torrisi, November 18, 2003
 Speaker

Fabio Torrisi,
Automatic Control Laboratory,
Swiss Federal Institute of Technology,
Zurich, Switzerland.
 Date and Time

Tuesday, November 18, 2003 at 15:45
 Place

Aula Seminari,
Dipartimento di Matematica,
Università di Parma,
Via D'Azeglio 85/A,
I43100 Parma
 Title

Convexity Recognition of the Union of Polyhedra
 Abstract

In this talk, we consider the following basic problem in polyhedral
computation: Given two polyhedra in finite dimension, P and Q, decide
whether their union is convex, and, if so, compute it. We consider the
three natural specializations of the problem:
 when the polyhedra are given by halfspaces (Hpolyhedra),
 when they are given by vertices and extreme rays (Vpolyhedra), and
 when both H and Vpolyhedral 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 is stronglypolynomially solvable.
 Slides

Convexity Recognition of
the Union of Polyhedra (pdf, 1402 kB).
 Links to Related Publications
 Contact Person

Roberto Bagnara
[Page last updated on November 22, 2003, 10:38:50.]
