|
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:
- when the polyhedra are given by halfspaces (H-polyhedra),
- when they are given by vertices and extreme rays (V-polyhedra), and
- 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
- Contact Person
-
Roberto Bagnara
[Page last updated on November 22, 2003, 10:38:50.]
|