CS Events Monthly View

Seminar

The Power of Preprocessing: Detecting and constructing intersections between geometric objects

 

Download as iCal file

Wednesday, March 04, 2015, 11:00am

 

When solving a computational problem (e.g., finding an element in a set), it is often the case that the bulk of the data used for input for the problem (e.g., the set) is known well in advance. By preprocessing the data (e.g., sorting the set), it is often possible to significantly reduce the time needed to solve the problem once the specific query is provided.

In this lecture, 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 cannot.

Speaker: Stefan Langerman

Bio

NULL

Location : CoRE A (Room 301)

Committee

Swastik Kopparty and Shubhangi Saraf

Event Type: Seminar

Abstract: 

Organization

Free University of Brussels