Maximum Overlap of Convex Polytopes under Translation

Speaker:	Professor Siu-Wing CHENG
		Department of Computer Science & Engineering
		Hong Kong University of Science & Technology

Title:		"Maximum Overlap of Convex Polytopes under Translation"

Date:		Monday, 25 October 2010

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F (near lifts 25/26), HKUST

Abstract:

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 R^3.  All bounds and their big-O constants are
independent of epsilon.

This is joint work with Hee-Kap Ahn and Iris Reinbacher


******************
Biography:

Prof. Siu-Wing Cheng obtained his BSc (Computer Studies) from the
University of Hong Kong in 1987 and his PhD in Computer Science from the
University of Minnesota in 1992.  Prof. Cheng has been affiliated with
HKUST since then.  His recent research interests include algorithmic
problems in mesh generation, manifold reconstruction, and computational
geometry in general.