[PPL-devel] Two seminars on computational geometry
Roberto Bagnara
bagnara at cs.unipr.it
Mon Oct 27 20:06:38 CET 2003
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
More information about the PPL-devel
mailing list