SEMINARS OF THE "PARMA POLYHEDRA LIBRARY" PROJECT =================================================

TWO SEMINARS ON COMPUTATIONAL GEOMETRY --------------------------------------

A cycle of seminars on topics related to the "Parma Polyhedra Library" project (http://www.cs.unipr.it/ppl) will take place in the coming months at the Department of Mathematics of the University of Parma. The announcements of the first two seminars in the series follow.

----------------------------------------------------------------------

Date: Tuesday, November 18th, 2003

Time: 14:30

Speaker: Fabio Torrisi ETH Zurich

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.

Place: Sala Riunioni Department of Mathematics University of Parma Via D'Azeglio, 85/A Parma, Italy

======================================================================

Date: Tuesday, November 18th, 2003

Time: 15:45

Speaker: Fabio Torrisi ETH Zurich

Title: Inner and Outer Approximations of Polytopes Using Boxes

Abstract: The talk deals with the problem of approximating a convex polytope in any finite dimension by a collection of (hyper)boxes. More exactly, given a polytope P by a system of linear inequalities, we look for two collections I and E of boxes with non-overlapping interiors such that the union of all boxes in I is contained in P and the union of all boxes in E contains P. We propose and test several techniques to construct I and E aimed at getting a good balance between two contrasting objectives: minimize the volume error and minimize the total number of generated boxes. We suggest how to modify the proposed techniques in order to approximate the projection of P onto a given subspace without computing the projection explicitly.

Place: Sala Riunioni Department of Mathematics University of Parma Via D'Azeglio, 85/A Parma, Italy

----------------------------------------------------------------------

Information on all the seminars organized by the Computer Science Group of the University of Parma (http://www.cs.unipr.it) are available at http://www.cs.unipr.it/Seminars. It is possible to regularly receive the seminar's announcements by subscribing to the (strictly moderated) mailing list seminars@cs.unipr.it (http://www.cs.unipr.it/mailman/listinfo/seminars).