Chair of Theoretical Computer Science
The main area of research in this unit is the design and the analysis of efficient algorithms and data structures, especially for geomtric problems. Typical examples are computational problems involving higher-dimensional polyhedra, localizing query points amidst a very large number of geometric objects, and approximative geometric query answering. As ancillary subjects we also study combinatorial geometry and randomization.
Currently the following more specific topics are being investigated: the efficient encoding of complicated geometric data structures such as triangulations, complexes, or arrangements; computations with complicated geometric objects such as ellipsoids; geometric algorithms in the ``transdichotomous model'', i.e. the exploitation of the limited parallelism provided by the usual computer word operations.
Raimund Seidel, Micha Sharir
Top-Down Analysis of Path Compression. pdf
SIAM Journal of Computing.
Raimund Seidel, Udo Adamy
On the Exact Query Complexity of Planar Point Location. pdf
Journal of Algorithms, pp. 189-217.
Markus Denny, Christian Sohler
Encoding a triangulation as a permutation of its point set. pdf
Proc. 9th Canad. Conf. Comput. Geom., pp. 39-43.
David Avis, David Bremner, Raimund Seidel
How good are convex hull algorithms? pdf
Comput. Geom. Theory and Appl., pp. 265-302.
Raimund Seidel, Cecilia Aragon
Randomized Search Trees. pdf
Algorithmica 16, pp. 464-497.
A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. pdf
Comput. Geom. Theory and Appl., pp. 51-64.
to Fachrichtung 6.2