Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Thursday, December 06, 2007, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Andreas Razen
Let P be a set of n points in general position in the plane. We show that there is a constant eps > 0 such that a uniformly at random chosen crossing-free geometric graph on P contains in expectation at least a (1/2+eps)-fraction of the number of edges in a triangulation of P.
Hereby we derive (to our knowledge) the first non-trivial constant c>0 such that the number of crossing-free geometric graphs on P is at most c^n times more than the number of triangulations of P. By trivial we mean that the estimate clearly holds if we choose c such that c^n=2^M, where M is the number of edges in a triangulation of P. For a triangular convex hull of P, where M=3n-6, we obtain a constant c<7.98. As the previous upper bounds for the number of crossing-free geometric graphs on planar point sets were derived using the trivial 8^n factor, we can now slightly decrease this bound to O(343.11^n).
Joint work with Jack Snoeyink and Emo Welzl.
Automatic MiSe System Software Version 1.4803M | admin login