## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, September 16, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Luis Barba (Carleton University / Université Libre de Bruxelles)

## Detecting intersections between convex polyhedra

In this talk, we revisit the classic problem of preprocessing polyhedra independently so that given two preprocessed polyhedra $P$ and $Q$ in $R^d$ each translated and rotated, their intersection can be tested rapidly. For $d=3$ we show how to perform such a test in $O(\log |P| + \log |Q|)$ time after linear preprocessing time and space. This running time is the best possible and improves upon the last best known query time of $O(\log|P| \log|Q|)$ by Dobkin and Kirkpatrick (1990).

We then generalize this method to any constant dimension $d$, achieving the same optimal $O(\log |P| + \log |Q|)$ query time using a representation of size $O(|P|^{\lfloor d/2 \rfloor +\epsilon})$ for any $\epsilon > 0$ arbitrarily small. This answers an even older question posed by Dobkin and Kirkpatrick 30 years ago.

Information for students and suggested topics for student talks