 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, January 31, 2006, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Takeaki Uno (National Institute of Informatics (NII)

## Maximization Problem of Intersection of Polytopes

Let A and B are two polygons in Euclidean plane where the position of A is fixed and the body B can be translated freely. Then, the intersection of A and B changes as the move. Here we consider the intersection maximization problem, that is, to maximize the volume of the intersection by translation. This problem is easy to state, but it appears that it has not been investigated in depth. In fact, this problem has been recently proposed as an open problem at an Oberwolfach workshop by P. Brass. The volume of the intersection has both features of convex and concave functions, and not differential at some points, thus the maximization is not straightforward.

We will show that the dth root of the volume is concave for any finite number of d-dimensional convex polytopes. We also show that the hyperplanes spanned by the facets of the polytopes define an arrangement where the objective function is a simple polynomial function in each of its regions. By using these properties, we propose a strongly polynomial time algorithm for the case of two convex polygons in the plane. Its time complexity is O(n2 log2 n) and its space complexity is O(n) if they both have at most n edges. We further propose an enumeration based algorithm for the problem with two non-convex polygons which runs in O(n4) time and O(n2) space.

(Joint work with Komei Fukuda)

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks