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

Prof. Emo Welzl and Prof. Bernd Gärtner

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)

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(n^{2} log^{2} 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(n^{4}) time and O(n^{2}) 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