Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

No Title


Lower bounds for geometric computations

R. Seidel, Universität des Saarlandes

We give a survey of methods and results pertaining to bounding from below the computational complexity of geometric problems. The methods include information theoretic approaches, reductions, adversary arguments for special computational models, and combinatorial arguments for the so-called semi-group model.


Theoretical Computer Science Back