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, I-43100 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:

1. when the polyhedra are given by halfspaces (H-polyhedra),
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 is strongly-polynomially solvable.

Slides

Convexity Recognition of the Union of Polyhedra (pdf, 1402 kB).

Links to Related Publications

• Convexity Recognition of the Union of Polyhedra;
• Fabio Torrisi's PhD thesis.

Contact Person

Roberto Bagnara

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