Title: The Power of (Geometric) Preprocessing 

Speaker: Stefan Langerman, Université Libre de Bruxelles

Time/Date: Thursday, May 29, 11-12
Location: Room 3501

Abstract:

When solving a computational problem, it is often the case that the
bulk of the data used for input for the problem is known well in
advance.  By \emph{preprocessing} the data, it is sometimes possible
to significantly reduce the time needed to solve the problem once the
specific query is provided.

In this talk, I will focus on some of the most fundamental problems
in Computational Geometry -- determining if geometric objects
intersect, and if they do what is, or how large is, their intersection.
These problems are fairly well understood in the traditional setting where
two objects are provided and the intersection must be returned as output.

However it may be the case that each object is known long in advance,
and is translated and rotated just prior to the intersection query.
For that setting, I will review some known and new results in an
attempt to determine when preprocessing helps, and when it does not.

This is joint work with Luis Barba.