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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 1998

Arbeitsgruppe Prof. Dr. Emo Welzl
November 1998

Institut für Theoretische Informatik
Departement Informatik
ETH Zürich
CH-8092 Zürich


Mitglieder

  1. Professor:
    - Welzl, Emo, Dr.

  2. Wissenschaftliche Mitarbeiter (Doktoranden mit Arbeitstitel der Dissertation):
    - Ambühl, Christoph (seit 15. August 1998)
    - Andrzejak, Artur - Das k-Mengenproblem für Punktmengen.
    - Blömer, Johannes, Dr. (Oktober 1997 - März 1998: Vertretung einer Professur an der Universität Frankfurt)
    - Brehm, Enno (20. Oktober 1997 - 6. Februar 1998)
    - Gärtner, Bernd, Dr. (1. Juli - 31. August 1998 Mitarbeit am GIF-Projekt ``Polytope und Optimierung'', geleitet von Prof. Günter Ziegler an der Technischen Universität Berlin.)
    - Giesen, Joachim - Kurvenrekonstruktion.
    - Hoffmann, Michael
    - Karolyi, Gyula, Dr. (1. Oktober 1997 - 28. Februar 1998)
    - Kettner, Lutz - Konturkanten-basiertes Entfernen verdeckter Flächen.
    - von Stengel, Bernhard, PD Dr. (bis 15. September 1998)
    - Trachsler, Beat - Ausfalltolerante Codes und sichere Datenübertragung auf dem Internet.
    - Tschirschnitz, Falk (seit 1. August 1998)
    - Will, Hans-Martin - Algorithmen zu Problemen der Molekülgeometrie. (bis 30. September 1998)

  3. Sekretariat:
    - Krenn, Tanja


Gäste und Vorträge

GÜNTER ZIEGLER, Technische Universität Berlin, Deutschland (12. Januar 1998).
Lattice Polytopes and Triangulations.

ANDREAS DRESS, Universität Bielefeld, Deutschland (26. Januar 1998).
Highly regular spatial structures: theory, software, and visualization.

HELMUT ALT, Freie Universität Berlin, Deutschland (15. Februar bis 15. März 1998).
Point sets with few k-sets.
Nearest neighbor search in high dimensions.

FRANK WAGNER, Freie Universität Berlin, Deutschland (2. April bis 3. Mai 1998).
Mimicking Networks.

JACK SNOEYINK, INRIA Sophia-Antipolis, Frankreich & Univ. of British Columbia (15. April bis 24. April 1998).
On the primitives required for efficient segment intersection algorithms.
An open problem on points and segments in the plane, and where it comes from.

ANTOON VAN DEN ELZEN, Department of Econometrics, Tilburg University, Niederlande (16. Mai bis 22. Mai 1998).
Introduction to simplicial algorithms and an application to game theory.

JÍRI MATOUSEK, Charles University Prag, Tschechische Republik (1. Mai bis 31. Juli 1998).
Noga Alon on the Shannon capacity of a disjoint union.
Graphs without small complete bipartite subgraphs (according to Kollar, Ronyai, Szabo, and Alon).

IMRE BARANY, Mathematical Institute of the Hungarian Academy of Science, Budapest (8. Juni bis 10. Juni 1998).
How many convex lattice polytopes are there?
Spiral in Geodesics.

OTFRIED CHEONG, The Hong Kong University of Science and Technology, China (15. Juni bis 24. Juli 1998).
Hierarchische vertikale Zerlegungen.

KAROLYI GYULA, Department of Algebra and Number Theory, Eotvos University, Budapest (24. August bis 30. August 1998).

STEFAN FELSNER, Freie Universität Berlin, Deutschland (7. September bis 13. September 1998).
Graphs and Poset-Dimension.
Reduzierte Dekompositionen und Young Tableaux.

LEONIDAS GIUBAS, Stanford University, Palo Alto, USA (21. September 1998).
Collision Detection.



Drittmittel


Veröffentlichungen und Vorträge

  1. Veröffentlichungen in Zeitschriften (mit Auswahlverfahren)

    A. ANDRZEJAK, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Mathematics 190, 1998, 39-54.

    B. GäRTNER, S. SCHöNHERR, Exact primitives for smallest enclosing ellipses, Information Processing Letters 68, 1998, 33-38.

    B. GäRTNER, M. HENK, G. M. ZIEGLER, Randomized simplex algorithms on Klee-Minty cubes, Combinatorica 18, 1998, 349-372.

    O. SCHWARZKOPF, U. FUCHS, G. ROTE, E. WELZL, Approximation of convex figures by pairs of rectangles, Computational Geometry - Theory and Applications 10, 1998, 77-87.

    P.K. AGARWAL, M. SHARIR, E. WELZL, The discrete 2-center problem, Discrete Comput. Geom. 20, 1998, 287-305.

    L.P. CHEW, K. KEDEM, M. SHARIR, B. TAGANSKY, E. WELZL, Voronoi diagrams of lines in three dimensions under a polyhedral convex distance function, J. Algorithms 29, 1998, 238-255.


  2. Veröffentlichungen in Konferenzbänden (mit Auswahlverfahren)

    A. ANDRZEJAK, B. ARONOV, S. HAR-PELED, R. SEIDEL, E. WELZL, Results on k-sets and j-facets via continuous motions, in Proc. 14th Annual ACM Symposium on Computational Geometry (SoCG '98), 1998, 192-199.

    J. BLÖMER, A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers, in Proc. 6th Annual European Symposium on Algorithms (ESA '98), 1998, 159-162.

    B. GÄRTNER, Exact Arithmetic at Low Cost - A Case Study in Linear Programming, in Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998, 157-166.

    B. GÄRTNER, Combinatorial Linear Programming: Geometry can Help, in Proc. 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM`98), Lecture Notes in Computer Science 1518, 1998, 82-96.

    L. KETTNER, Designing a Polyhedral Surface Data Structure in C++, in Proc. 14th Annual ACM Symposium on Computational Geometry (SoCG '98), 1998, 146-154.

    H.-M. WILL, Fast and Efficient Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology, in Proc. of the 6th Scandinavian Workshop on Algorithms Theory (SWAT'98), Lecture Notes in Computer Science 1432, 1998, 310-311.


  3. Sonstige Veröffentlichungen

    A. ANDRZEJAK, Introduction to randomized algorithms, Lecture Notes in Computer Science 1367, 1998, 29-39.

    A. ANDRZEJAK, E. WELZL, Halving point sets, Documenta Mathematica, Extra Volume ICM 98, Proceedings of the International Congress of Mathematicians Berlin, 1998, Vol. III, 471-478.

    J. GIESEN, Electric dipole moments of elementary particles and irreducible representations of the poincare group, Photon and Poincare Group, Valeri Dvoeglazov Editor, Nova Science Publisher, 1998.

    L. KETTNER, E. WELZL, One sided error predicates in geometric computing, in Proc. 15th IFIP World Computer Congress, Fundamentals - Foundations of Computer Science (K. Mehlhorn, Ed.), 1998, 13-26.


  4. Berichte

    308
    H. BRÖNNIMANN, L. KETTNER, S. SCHIRRA, R. VELTKAMP, Applications of the Generic Programming Paradigm in the Design of CGAL (1998).

    302
    H.-M. WILL, Geometric Properties of Spatial Additively Weighted Voronoi Cells (1998).

    300
    H.-M. WILL, Practical and Efficient Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology (1998).

    299
    J. BLÖMER, A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers (1998).

    298
    J. BLÖMER, B. TRACHSLER, A Lower Bound for a Class of Graph Based Loss-Resilient Codes (1998).

    296
    B. GÄRTNER, V. KAIBEL, Abstract Objective Function Graphs on the 3-cube - A Classification by Realizability (1998).

    291
    B. FABRI, G.-J. GIEZEMAN, L. KETTNER, S. SCHIRRA, S. SCHÖNHERR, On the Design of CGAL, the Computational Geometry Algorithms Library (1998).

    283
    B.GÄRTNER, Exact Arithmetic at Low Cost - A Case Study in Linear Programming (1998).


  5. Vorträge

    C. AMBÜHL
    - "Towards a new lower bound in the list update problem", Workshop on On-line Algorithms, Udine, Italien (5. September 1998).

    A. ANDRZEJAK
    - "K-sets and their applications", Departement de Mathematiques Ecole Polytechnique Federale de Lausanne, Schweiz (19. August 1998).

    J. BLÖMER
    - "Sichere Datenübertragung auf dem Internet und effiziente ausfalltolerante Codes", Mathematikkolloquim Johann Wolfgang Goethe-Universität Frankfurt, Deutschland (23. Januar 1998).
    - "Effiziente ausfalltolerante Codes mit Hilfe zufälliger Graphena", Statistikkolloquim Johann Wolfgang Goethe-Universität Frankfurt, Deutschland (26. Januar 1998).
    - "Sichere Datenübertragung auf dem Internet und effiziente ausfalltolerante Codes", Informatikkolloquim Universität Paderborn, Deutschland (16. März 1998).
    - "A probabilistic zero-test for expressions involving roots of rational numbers", 6th Annual European Symposium on Algorithms, Venedig, Italien (24. August 1998).
    - "On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice", Mathematisches Forschungsinstitut Oberwolfach, Deutschland (16. November 1998).
    - "Vereinfachungen von Radikalausdrücken", Fachbereich Mathematik, Universität Paderborn, Deutschland (7. Dezember 1998).
    - "Gitterprobleme in der Kryptographie und Komplexitätstheorie", Seminarzyklus zur Theoretischen Informatik, Departement Informatik, ETH Zürich, Schweiz (11. Dezember 1998).

    B. GÄRTNER
    - "Exact Arithmetic at Low Cost - A Case Study in Linear Programming", 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, USA (25. Januar 1998).
    - "Abstract Objective Functions", Workshop on Discrete Mathematics (DM'98), Humboldt-Universität zu Berlin, Deutschland (25. April 1998).
    - "Combinatorial Linear Programming: Geometry can Help", 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM`98) , Barcelona, Spanien (8. Oktober 1998).
    - "Randomisierte Optimierung - Neue Hoffnung für ein altes Problem?", Seminarzyklus zur Theoretischen Informatik, Departement Informatik, ETH Zürich, Schweiz (11. Dezember 1998).

    J. GIESEN
    - "Parameter-Free Geometry of One-Manifolds", Berlin, Deutschland (22. August 1998).

    G. KAROLYI
    - "Talagrand's isoperimetric theory and its applications", Seminaire en recherche operationnelle EPF Lausanne, Lausanne, Schweiz (18. Februar 1998).
    - "The subset sum problem in combinatorial number theory", Université Genève, Schweiz (19. Februar 1998).
    - "Ramsey-remainder for convex sets and the Erdös-Szekeres Theorem", Seminar on Combinatorial Computing, City College, CUNY, New York, USA (18. März 1998).
    - "Crossing-free segments and triangles in point configurations", Universitat Politècnica de Catalunya, Spanien (25. März 1998).

    L. KETTNER
    - "Designing a Polyhedral Surface Data-Structure in C++", Dagstuhl Seminar on "Programs with Recursively Defined Data Structures", Dagstuhl, Deutschland (22. April 1998).
    - "Designing a Polyhedral Surface Data Structure in C++", 14th Annual ACM Symposium on Computational Geometry, Minneapolis, USA (8. Juni 1998).
    - "CGAL: The Computational Geometry Algorithms Library", Doktorandenkolloquium der Interuniversitären Partnerschaft Erdbeobachtung und Geoinformatik (IPEG), ETH Zürich, Schweiz (17. November 1998).

    B. VON STENGEL
    - "Spieltheorie zum Mitmachen: Preisbildung im Duopol", Kolloquium über Mathematik, Informatik und Unterricht, ETH Zürich (22. Januar 1998).
    - "Functional Decomposition in Logic Design and Operations Research", Kolloquium über Kombinatorik, Geometrische Algorithmen und Optimierung, ETH Zürich (2. Februar 1998).
    - "Improved Equilibrium Enumeration for Bimatrix Games", Theory Seminar, Division of the Humanities and Social Sciences, California Institute of Technology, Pasadena, USA (23. Februar 1998).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", Mathematics Seminar, University of California at Los Angeles, USA (24. Februar 1998).
    - "Team-Maxmin Equilibria", Game Theory working group seminar, Stanford Business School, USA (16. März 1998).
    - "Team-Maxmin Equilibria", Special Joint Computer Science Theory / Economic Theory Seminar, University of California at Berkeley, USA (18. März 1998).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", International Computer Science Institute, Berkeley, USA (19. März 1998).
    - "Efficient computation of equilibria for game trees", Mathematics Seminar, London School of Economics, England (31. März 1998).
    - "Effiziente Lösung von Spielbäumen", Kolloquium Informatik, Universität Bonn, Deutschland (4. Mai 1998).
    - "Wieviele Gleichgewichte kann ein Bimatrixspiel haben? Neue Resultate mit Polytoptheorie", Kolloquium Mathematik und Informatik, Universität Passau, Deutschland (5. Mai 1998).
    - "Wieviele Gleichgewichte kann ein Bimatrixspiel haben? Neue Resultate mit Polytoptheorie", Arbeitsgemeinschaft Diskrete Mathematik, Technische Universität München, Deutschland (6. Mai 1998).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", Interdisciplinary Seminar in Game Theory, London School of Economics, England (9. Juni 1998).
    - "Improved Bounds for Equilibrium Enumeration Using Polytope Theory", 8th International Symposium on Dynamic Games and Applications, Maastricht, Niederlande (8. Juli 1998).
    - "Improved Equilibrium Enumeration for Bimatrix Games", International Conference on Operations Research OR 98, ETH Zürich (1. September 1998).
    - "Team-Maxmin Equilibria", Interdisciplinary Seminar in Game Theory, London School of Economics, England (26. November 1998).

    E. WELZL
    - "Der Graph halbierender Kanten ebener endlicher Punktemengen und verwandte Probleme", Johann Wolfgang Goethe-Universität Frankfurt, Frankfurt, Deutschland (16. Januar 1998).
    - "The Graph of Halving Edges", Seminaire en recherche operationnelle EPF Lausanne, Lausanne, Schweiz (18. Februar 1998).
    - "n Points Meet n Lines", Junior Mathematical Congress (JMC `98), Potsdam, Deutschland (20. August 1998).
    - "Halving Point Sets", International Congress of Mathematicians (ICM `98), Berlin, Deutschland (21. August 1998, eingeladener Vortrag, Sektion Mathematics of Computation).
    - "One Sided Error Predicates in Geometric Computing", 15th IFIP World Computer Congress, Wien, Österreich (31. August 1998, eingeladener Vortrag).
    - "On a Simple Sampling Lemma", 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM`98) , Barcelona, Spanien (10. Oktober 1998, eingeladener Vortrag).
    - "j-Facetten endlicher Punktemengen und das Upper Bound Theorem für konvexe Polytope", Informatik Kolloquium, Universität Bern, Schweiz (24. November 1998).
    - "j-Facets of Finite Point Configurations and the Upper Bound Theorem for Polytopes", Ecole Polytechnique, Paris, Frankreich (26. November 1998).

    H.-M. WILL
    - "Robust and efficient computation of additively weighted Voronoi cells", European Bioinformatics Institute, Hinxton Hall, Cambridge (17. September 1998).


Vorlesungen und Seminare (WS 97/98 und SS 98)

J. BLÖMER, B. GÄRTNER
- Approximationsalgorithmen (Vorlesung und Übung SS 98)

B. GÄRTNER, E. WELZL
- Algorithmische Geometrie (Vorlesung und Übung WS 97/98)

B. VON STENGEL
- Algorithmen in der Spieltheorie (Vorlesung und Übung WS 97/98)
- Informatik II (Vorlesung und Übung SS 98)

E. WELZL
- Informatik I für III B (Abteilung Elektrotechnik)(Vorlesung und Übungen WS 97/98)
- Geometrisches Rechnen (Vorlesung und Übung SS 98)
- Theoretische Informatik (Vorlesung und Übung SS 98)


Diplomarbeiten


Semesterarbeiten


Sonstiges

A. ANDRZEJAK
- Mitglied in der Hochschulversammlung (als Delegierter der AVETH) in der Arbeitsgruppe "Leistungsauftrag".

J. GIESEN
- Assistent für die Vorlesung Logik der Abt. IIIc im WS 97/98.

M. HOFFMANN
- Assistent für die Vorlesung Informatik I der Abt. IIIb im WS 97/98.

L. KETTNER
- Assistent für die Vorlesung Informatik I der Abt. IIIb im WS 97/98.

B. VON STENGEL
- Associate Editor von Mathematics of Operations Research
- Gründungsmitglied der Game Theory Society

B. TRACHSLER
- Assistent für die Vorlesung Informatik I der Abt. IIIb im WS 97/98.

E. WELZL
- Mitglied des Editorial Boards von

- Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI)
- Vorsitzender des Gödel Prize Committee (SIGACT ACM und EATCS)
- Mitglied des Programmkommitees Eurographics '98, (Lissabon, Portugal, 31. August - 4. September 1998).
- Mitglied des Programmkommitees of the 39th Annual Symposium on Foundations of Computer Science (Palo Alto, California, USA, 8.-11. November 1998).
- Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Effiziente Algorithmen für Diskrete Probleme und ihre Anwendungen" der Deutschen Forschungsgemeinschaft (DFG)
- Mitglied der Dozentenkommission der ETH Zürich.
- Vorsteher des Instituts für Theoretische Informatik der ETH Zürich.

H.-M. WILL
- Frauenförderung im WS 97/98.



Tanja Krenn
Wed, Jan 7, 10:55 MET DST 1998