Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 25, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Jiří Matoušek (Charles Univ., Prague)
A zone diagram is a new variation of the classical notion of Voronoi diagram. Given points (sites) p_1,...,p_n in the plane, each p_i is assigned a region R_i, but in contrast to the ordinary Voronoi diagrams, the union of the R_i has a nonempty complement, the neutral zone. The defining property is that each R_i consists of all points that lie closer (non-strictly) to p_i than to the union of all the other R_j. Thus, the zone diagram is defined implicitly, by a fixed-point property, and neither its existence nor its uniqueness seem obvious. We prove both, as well as convergence of a natural iterative algorithm for computing it. Many challenging questions remain open.
Joint work with Tetsuo Asano and Takeshi Tokuyama.
Automatic MiSe System Software Version 1.4803M | admin login