Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login