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

Date and Time: Tuesday, October 29, 2019, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Raphael Wegner

Queries for convex Polytopes

Consider a collection of convex polytopes. After independently preprocessing each polytope in time that is linear in the number of vertices n, we want to efficiently (i.e., in polylogarithmic time) answer different queries concerning the interaction of several polytopes, after each of them has gone through an affine transformation. We provide an algorithm for detecting a common intersection of three convex polytopes in three dimensions with a query time of O(log²(n)). Additionally, we simplified an existing algorithm for the same problem but concerning two polytopes, running in optimal time O(log(n)). Further, the thesis includes an optimal algorithm for linear programming in the intersection of two polygons in time O(log(n)), as well as an O(log²(n)) algorithm for linear programming in the intersection of two polytopes in three dimensions.

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