Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 21, 2006, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Jan Remy
Given a set of points P in the plane with non-negative profits (or prizes) we want to select a maximum profit subset X of P which maximizes the total profit of the points in X minus some criterion z(X). In this talk we consider four such criteria, namely the perimeter and the area of the smallest axis-parallel rectangle containing X, and the perimeter and the area of the convex hull of X. In particular, we show how to compute a set of maximum profit with respect to perimeter of the smallest enclosing axis-parallel rectangle in O(n^2 log n) time using O(n) space.
Joint work with Stefanie Gerke.
Automatic MiSe System Software Version 1.4803M | admin login