Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 07, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Kevin Buchin (FU Berlin)
For the incremental construction of Delaunay triangulations, we prove that combining locality and randomness yields a linear expected time algorithm for uniformly distributed points. The points are inserted in random rounds and within rounds along space-filling curves. Point location along a space-filling curve allows to make use of locality while maintaining a good distribution of the points. For higher dimensions we prove that randomized incremental construction can be done in linear expected time.
Automatic MiSe System Software Version 1.4803M | admin login