[Mittagsseminar TI] Seminar tomorrow Thursday, 16:15 Uhr, N. Rubin on kinetic Delaunay triangulations

[Günter Rote <rote@inf.fu-berlin.de>]

Special "MIttagsseminar":

Thursday, June 27, 16:15-17:30 Uhr, Seminarraum 005, Takustraße 9

Natan Rubin, Freie Universität Berlin

On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit-Speed Motions

Let P be a collection of n points in the plane, each moving along some straight line and 
at unit speed. We obtain an almost tight upper bound of O(n^{2+epsilon}), for any 
epsilon>0, on the maximum number of discrete changes that the Delaunay triangulation of P 
experiences during this motion. Our analysis is cast in a purely combinatorial setting, 
where we only assume that (i) any four points can be co-circular at most three times, and 
(ii) no triple of points can be collinear more than twice; these assumptions hold for unit 
speed motions.

--
G"unter Rote