报告题目: |
Maximum Overlap of Convex Polytopes under Translation |
报告人: |
Prof. Siu-Wing Cheng |
|
The Hong Kong University of Science and Technology
|
报告时间: |
2010-10-21 15:00 |
报告地点: |
理科楼1304报告厅 |
主办单位: |
数学科学系 |
简介: |
We study the problem of maximizing the overlap of two convex polytopes under translation in R^d for some constant d >= 3. Let n be the number of bounding hyperplanes of the polytopes. We present an algorithm that, for any epsilon > 0, finds an overlap at least the optimum minus epsilon and reports a translation realizing it. The running time is O(n^{1 + d/2} log n) with probability at least 1 - 1/n^O(1), which can be improved to O(n (log n)3.5) in R3. All bounds and their big-O constants are independent of epsilon. This is joint work with Hee-Kap Ahn and Iris Reinbacher . |
|
