Research

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.

Courses

WS 11/12

• Lecture: Algorithms and Data Structures

  SS 12

• Proseminar: Perlen der Theoretischen Informatik

• Past Terms (german)

People

• Head

  Raimund Seidel
  Building E1 3, Room 409
  Phone: +49 (681) 302-4513
  Office hour: Mo, Fr 11:00-12:00
  E-mail:rseidel at cs.uni-saarland.de
  
  

• Staff

  Sascha Parduhn
  Room 414
  Phone: +49 (681) 302-4447
  E-mail:parduhn at cs.uni-saarland.de
  
  
  Victor Alvarez
  Room 412
  Phone: +49 681 302 5578
  E-mail:alvarez at cs.uni-sb.de
  
  
  László Kozma
  Room 416
  Phone: +49 681 302 3420
  E-mail:kozma at cs.uni-saarland.de
  
  

• Former Staff

  Wei Ding
  
  E-mail:wding at cs.uni-sb.de
  
  
  Ulrike Lehmberg
  
  E-mail:lehmb at cs.uni-sb.de
  
  
  Dierk Johannes
  
  E-mail:johannes at cs.uni-sb.de
  
  
  Nicola Wolpert
  
  E-mail:nicola at mpi-sb.mpg.de
  
  
  Markus Denny
  
  E-mail:mdenny at cs.uni-sb.de
  
  
  Frank Lehmann
  
  E-mail:lehmann at cs.uni-sb.de
  
  
  Saurabh Ray
  
  E-mail:saurabh at cs.uni-sb.de
  
  
  Hans Raj Tiwary
  
  E-mail:hansraj at cs.uni-sb.de
  
  
  Jörg Lässig
  
  E-mail:laej at cs.uni-sb.de
  
  

• Former Students

  Alexander Malkis
  
  
  
  Ralf Osbild
  
  E-mail:osbild at mpi-sb.mpg.de
  
  
  Udo Adamy
  
  
  
  Torsten Bücheler
  
  E-mail:mac at cs.uni-sb.de
  
  
  Jochen Comes
  
  E-mail:comi at cs.uni-sb.de
  
  
  Armin Juhlke
  
  
  
  Paul McCabe
  
  
  
  Christian Sohler
  
  E-mail:csohler at uni-paderborn.de
  
  
  Mark Ziegelmann
  
  
  

Selected Publications

• Raimund Seidel, Micha Sharir
  Top-Down Analysis of Path Compression. ps.gz
  To appear in SIAM Journal of Computing.
  

  
  

• Raimund Seidel, Udo Adamy
  On the Exact Query Complexity of Planar Point Location. ps.gz
  Journal of Algorithms 37, pp. 189-217, 2000.
  

  
  

• Raimund Seidel, Cecilia Aragon
  Randomized Search Trees ps.gz ps
  Algorithmica 16 (1996) 464-497.
  

  
  

• Markus Denny, Christian Sohler
  Encoding a triangulation as a permutation of its point set ps.gz ps
  Proc. 9th Canad. Conf. Comput. Geom. (1997) 39-43.
  

  
  

• David Avis, David Bremner, Raimund Seidel
  How good are convex hull algorithms? ps.gz ps
  Comput. Geom. Theory and Appl. 7 (1997) 265-302.
  

  
  

• Raimund Seidel
  A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons ps.gz ps
  Comput. Geom. Theory and Appl. 1 (1991) 51-64.
  

  
  

Address and Route

Route to the university

Postal Address

Universität des Saarlandes
FR 6.2 Informatik
Prof. Dr. Raimund Seidel
Postfach 151150
D-66041 Saarbrücken
Germany

Visitors Address

Universität des Saarlandes
Im Stadtwald
Building E 1.3, 4.Stock, Zimmer 410
D-66123 Saarbrücken
Germany

Ressources

Computational Geometry Pages of Jeff Erickson
Computational Geometry on the World Wide Web by Guilherme Albuquerque Pinto.