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

• Winter Term 2021/2022

• Lecture "Grundzüge von Algorithmen und Datenstrukturen 21/22"

• Algorithm and Data Structures (block course)

---

• Past Terms

• Winter Term 2020/2021

• Lecture "Grundzuege Algorithmen und Datenstrukturen 20/21"

People

• Head

  Raimund Seidel
  E 1 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

  László Kozma
  Room 416
  Phone: +49 681 302 3420
  Office Hour: blank
  E-mail: kozma at cs.uni-saarland.de

  
  
  Giorgi Nadiradze
  Room 421
  Phone: +49 681 302 3235
  Office Hour:
  E-mail: gnadiradze at cs.uni-saarland.de
  
  
  Lavinia Dinu
  Room 416
  Phone: +49 681 302 3420
  Office Hour: Tu, Th 12:00-13:00
  E-mail: ldinu at cs.uni-saarland.de

• Former Staff

  Victor Alvarez Email: alvarez at cs.uni-sb.de

  
  

  Wei Ding Email: wding at cs.uni-sb.de

  
  

  Ulrike Lehmberg Email: lehmb at cs.uni-sb.de

  
  

  Dierk Johannes Email: johannes at cs.uni-sb.de

  
  

  Nicola Wolpert Email: nicola at mpi-sb.mpg.de

  
  

  Markus Denny Email: mdenny at cs.uni-sb.de

  
  

  Frank Lehmann Email: lehmann at cs.uni-sb.de

  
  

  Saurabh Ray Email: saurabh at cs.uni-sb.de

  
  

  Hans Raj Tiwary Email: hansraj at cs.uni-sb.de

  
  

  Jörg Lässig Email: laej at cs.uni-sb.de

  
  

  Sascha Parduhn Email: parduhn at cs.uni-sb.de

• Former Students

  Alexander Malkis

  
  

  Ralf Osbild Email: osbild at mpi-sb.mpg.de

  
  

  Udo Adamy

  
  

  Torsten Bücheler Email: mac at cs.uni-sb.de

  
  

  Jochen Comes Email: comi at cs.uni-sb.de

  
  

  Armin Juhlke

  
  

  Paul McCabe

  
  

  Christian Sohler Email: csohler at uni-paderborn.de

  
  

  Mark Ziegelmann

Selected Publications

• 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.
  




• Raimund Seidel
  A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. pdf
  Comput. Geom. Theory and Appl., pp. 51-64.
  

Address and Route

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