Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Friday, July 05, 2002, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Mordecai J. Golin (Hong Kong University of Science and Technology)
It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Theta(n^2). Interest has recently arisen as to what happens, both in deterministic and probabilistic situations, when the 3-dimensional points are restricted to lie on the surface of a 2-dimensional object. In this talk we consider the situation when the points are drawn from a 2-dimensional Poisson distribution with rate n over the surface of a polyhedron in 3-space. We show that with high probability the complexity of their Voronoi diagram is close is n polylog(n). This is joint work with Hyeonsuk Na.
Automatic MiSe System Software Version 1.4803M | admin login