Title: The Power of Preprocessing: Detecting and constructing intersections between geometric objects
Speaker: Stefan Langerman, Free University of Brussels
Date: Wednesday, March 4, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/