[cs at parma seminars] Two seminars on computational geometry

[Roberto Bagnara]

           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 at cs.unipr.it
(http://www.cs.unipr.it/mailman/listinfo/seminars).

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it