Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Wednesday, September 26, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Raimund Seidel (Saarland University)
Let $t(P)$ be the number of straight edge triangulations of a planar point set $P$. It is known that $t(P)\geq \Omega(2.4^n)$, where $n=|P|$. We give an algorithm that computes $t(P)$ in time $O(n^2 2^n)$. Thus the algorithm is ``aggregative'' in the sense that it determines the cardinality of a set substantially faster than by enumerating the elements.
Automatic MiSe System Software Version 1.4803M | admin login