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(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: 2025 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