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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 1997

Arbeitsgruppe Prof. Dr. Emo Welzl
Dezember 1997

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):
    - 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. (seit 1. April 1997)
    - Giesen, Joachim - Oberflächenrekonstruktion.
    - Hoffmann, Michael
    - Karolyi, Gyula, Dr. (1. Oktober 1997 - 28. Februar 1998)
    - Kettner, Lutz - Konturkanten-basiertes Entfernen verdeckter Flächen.
    - von Stengel, Bernhard, PD Dr.
    - Trachsler, Beat (seit 1. April 1997) - Ausfalltolerante Codes und sichere Datenübertragung auf dem Internet.
    - Will, Hans-Martin - Algorithmen zu Problemen der Molekülgeometrie.

  3. Sekretariat:
    - Krenn, Tanja


Gäste und Vorträge

LEONIDAS L. GUIBAS, Stanford University, USA (6. bis 9. Februar 1997).
Data Structures for Mobile Data.

OTFRIED SCHWARZKOPF, Postech, Pohang, Südkorea (28. Februar 1997).
Degneracies and canonicality in the randomized construction of delaunay triangulations.

JIRI MATOUSEK, Karlsuniversität Prag, Tschechische Republik (21. März bis 21. Juli 1997).

GÜNTER ROTE, Technische Universität Graz, Österreich (24. März bis 28. März 1997).
Matching convex shapes with respect to the symmetric difference.

BORIS ARONOV, Polytechnic University, Brooklyn, USA (1. April bis 30. April 1997).
Average Cost of Ray Shooting and Minimum-Area Triangulations.

SUSANNE ALBERS, Max-Planck-Institut für Informatik, Saarbrücken, Deutschland (18. April 1997).
Better Bounds for Online Scheduling.

MARY INABA, University of Tokyo, Japan (26. Mai bis 1. Juni 1997).
On geometric clustering problems.

ULRICH KORTENKAMP, Technische Universität Berlin, Deutschland (1. Juni bis 8. Juni 1997).

ALEXANDER BELOW, Cornell University, Ithaca, USA (16. Juni bis 13. Juli 1997).

RAIMUND SEIDEL, Universität des Saarlandes, Saarbrücken, Deutschland (26. Oktober bis 29. Oktober 1997).

PETRA MUTZEL, Max-Planck-Institut für Informatik, Saarbrücken, Deutschland (2. November bis 11. November 1997).

PETER GRITZMANN, TU München, Deutschland (23. November bis 25. November 1997).
Orakel-polynomial time approximation of radii and norm-maxima.

CHRISTOS PAPADIMITRIOU, UC Berkeley, USA (24. November bis 26. November 1997).
Market Segmentation Problems .

ALEXANDER SCHRIJVER, CWI Amsterdam, Niederlande (15. Dezember 1997).
Optimization at the Dutch Railways.


Drittmittel


Veröffentlichungen und Vorträge

  1. Veröffentlichungen in Zeitschriften (mit Auswahlverfahren)

    A. ANDRZEJAK, Splitting formulas for Tutte polynomials, Journal of Combinatorial Theory Series B 70, 1997, 346-366.

    T. ASANO, D. RANJAN, T. ROOS, E. WELZL, P. WIDMAYER, Space filling curves and their use in the design of geometric data structures, Theoretical Computer Science 181, 1997, 3-15.

    J. BLÖMER, R. KARP, E. WELZL, The rank of sparse random matrices over finite fields, Random Structures and Algorithms 10, 1997, 407-419.

    M. T. DICKERSON, R.L.S. DRYSDALE, S.A. McELFRESH, E. WELZL, Fast greedy triangulation algorithms, Computational Geometry - Theory and Applications 8, 1997, 67-86.

    H. EDELSBRUNNER, P. VALTR, E. WELZL, Cutting dense point sets in half, Discrete Comput. Geom. 17, 1997, 243-255.

    B. VON STENGEL, D. KOLLER, Team-maxmin equilibria. Games and Economic Behavior 21, 1997, 309-321.

    B. VON STENGEL, R. WERCHNER, Complexity of searching an immobile hider in a graph, Discrete Applied Mathematics 78, 1997, 235-249.


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

    P. AGARWAL, M. SHARIR, E. WELZL, The discrete 2-center problem, in "Proc. 13th Annual ACM Symposium on Computational Geometry", 1997, 147-155.

    J. BLÖMER, Denesting by bounded degree radicals, in "Proc. 5th Annual European Symposium on Algorithms", 1997, 53-63.

    L. KETTNER, E. WELZL, Contour Edge Analysis for Polyhedron Projections, Geometric Modeling: Theory and Practice, (W. Strasser, R. Klein, R. Rau, Eds.), (1997) 379-394, Focus in Computer Graphics, Springer Verlag.

    E. V. DUBROVA, J. C. MUZIO, B. VON STENGEL, Finding composition trees for multiple-valued functions, in Proc. 27th IEEE International Symposium on Multiple Valued Logic, 1997, 19-26.


  3. Sonstige Veröffentlichungen

    H. ALT, B. WOLFERS, E. WELZL, Piecewise linear approximations of Bézier-curves, communication, "Proc. 13th Annual ACM Symposium on Computational Geometry", 1997, 433-435.

    B. GÄRTNER, S. SCHÖNHERR, Exact Primitives for Smallest Enclosing Ellipses, communication, "Proc. 13. Annual ACM Symposium on Computational Geometry", 1997, 430-432.


  4. Berichte

    264
    B. VON STENGEL, New Lower Bounds for the Number of Equilibria in Bimatrix Games (1997).

    273
    J. BLÖMER, Denesting by Bounded Degree Radicals (1997).

    278
    L. KETTNER, Designing a Data Structure for Polyhedral Surfaces (1997).


  5. Vorträge

    A. ANDREZEJAK
    - "Randomisierte Algorithmen", GI-Forschungsseminar 1997 "Beweisverifikation und Approximationsalgorithmen", Dagstuhl, Deutschland (21.-28. April 1997).
    - "Diskussion um das Kryptoverbot", Sommerakademie der Studienstiftung des deutschen Volkes, Arbeitsgruppe "Rechtsfragen der Informationsgesellschaft", La Rochelle (2.-14. August 1997).

    J. BLÖMER
    - "Priority Encoding Transmission - Wie man mit Paketverlusten auf dem Internet umgehen kann", Informatikkolloquium Johann Wolfgang von Goethe Universität, Frankfurt, Deutschland (25. März 1997).
    - "Radikalvereinfachungsalgorithmen", Mathematikkolloquium Johann Wolfgang von Goethe Universität, Frankfurt, Deutschland (7. Mai 1997).
    - "Priority Encoding Transmission - Wie man mit Paketverlusten auf dem Internet umgehen kann", Kolloquium des Graduiertenkollegs "Algorithmische Diskrete Mathematik", Berlin, Deutschland (7. Juli 1997).
    - "Denesting by bounded degree Radicals", 5th Annual European Symposium on Algorithms, Graz, Österreich (15. September 1997).

    B. GÄRTNER
    - "Schranken für abstrakte Optimierungsprobleme", Theoretische Informatik und Logik, Schloss Münchenwiler, Murten, Schweiz (29.-30. April 1997).
    - "Linear Programming with Exact Arithmetic", Seminar "Effiziente Algorithmen", Oberwolfach, Deutschland (8. August 1997).
    - "Tail Estimates for Clarkson's Randomized LP Algorithm", International Symposium on Mathematical Programming, Lausanne, Schweiz (27. August 1997).
    - Neues über abstrakte Zielfunktionen auf dem Würfel, Fachbereich Mathematik, Technische Universität Berlin, Deutschland (16. Dezember 1997).

    M. HOFFMANN
    - "Computing Line Segment Intersections Exactly", Kolloquium über Aspekte der Implementation von Algorithmen, Konstanz, Deutschland (12. März 1997).

    L. KETTNER
    - "CGAL: Ein europäisches Projekt zum Entwurf einer Bibliothek geometrischer Algorithmen", Implementation Meeting, Universität Konstanz, Deutschland (24. Januar 1997).
    - "CGAL, die Bibliothek geometrischer Algorithmen: Ein europäisches Gemeinschaftsprojekt", eingeladener Vortrag, DFG Workshop on Aspects of the Implementation of Algorithms, Universität Konstanz, Deutschland (13. März 1997).
    - "Polyhedral Surface in CGAL", CGAL implementors meeting, INRIA, Sophia-Antipolis, Frankreich (27. Oktober 1997).
    - "Designing a Polyhedral Surface Data Structure in C++", Upper-Rhine-Region Algorithms Workshop, Universität Konstanz, Deutschland (14.-15. November 1997).

    B. VON STENGEL
    - "New Lower Bounds for the Number of Equilibria in Bimatrix Games", Vorlesungsreihe Algorithmische Geometrie, ETH Zürich, Schweiz (27. Januar 1997).
    - "Algorithms for Solving Extensive Form Games I & II", Summer School on Algorithms for the Theory of Games, Certosa di Pontignano, Siena, Italien (13.-14. Mai 1997).
    - "Neue Maximalzahlen von Gleichgewichten in Bimatrix-Spielen", Fakultät für Informatik, Universität der Bundeswehr München, Deutschland (25. Juni 1997).
    - "Selbstorganisierende Listen fuer Online-Zugriff", Oberseminar, Fakultät für Informatik, Universität der Bundeswehr München, Deutschland (27. Juni 1997).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", Management Science Seminar, CentER for Economic Research, Universität Tilburg, Niederlande (17. Juli 1997).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", International Symposium on Mathematical Programming, Lausanne, Schweiz (29. August 1997).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", Combinatorics Seminar, Department of Mathematics, University of Minnesota, Minneapolis, USA (25. September 1997).
    - "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games", Mathematical Economics Workshop, University of Minnesota, Minneapolis, USA (29. September 1997).
    - "Functional Decomposition in Multiple-Valued Logic and Operations Research", Department of Computer Science, University of Victoria, Kanada (3. Oktober 1997).
    - "Functional Decomposition in Multiple-Valued Logic and Operations Research", Department of Computer Science, University of Washington, Seattle, USA (9. Oktober 1997).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", Department of Mathematics, University of Washington, Seattle, USA (10. Oktober 1997).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", Algorithms Seminar, Department of Computer Science, Stanford University, USA (11. Oktober 1997).
    - "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games", Graduate School of Business, Stanford University, USA (15. Oktober 1997).
    - "New Maximal Numbers of Equilibria in Bimatrix Games", Ulric B. and Evelyn L. Bray Seminar, Division of the Humanities and Social Sciences, California Institute of Technology, Pasadena, USA (16. Oktober 1997).

    E. WELZL
    - "Schnelle Algorithmen - Wie macht man sie und wozu braucht man sie (noch)?", Antrittsvorlesung, ETH Zürich, Zürich, Schweiz (13. Januar 1997).
    - "Acht Damen und ein Würfel", Symposium Zur Kunst des Formalen Denkens im Rahmen der Ausstellung "jenseits von kunst", Palais Attems, Graz, Österreich (7. März 1997).
    - "Algorithmische Geometrie mit konservativen Prädikaten", Informatik Kolloquium der Universität Mannheim, Mannheim, Deutschland (7. Juli 1997).
    - "Visualization and Simulation", Short presentation of Task 4.2 (Workpackage Applications and Experimental Research) of the ESPRIT IV LTR Project CGAL, CGAL Review Meeting, Utrecht, Niederlande (25. August 1997).
    - "Computational Geometry", Equinoctial School "Geometry and Computation", ETH Zürich, Zürich, Schweiz (15. September 1997).
    - "Lösen geometrischer Probleme - einfach, stabil, schnell", Herbstschule "Was ist ein guter Algorithmus", Graduiertenkolleg Mathematische Optimierung, Universität Trier, Deutschland (9.-11. Oktober 1997).
    - "Continuous motion arguments for k-set bounds", Third Joint Meeting AMS-SMM, Oaxaca, Mexico, (3.-6. Dezember 1997).

    M. WILL
    - "Applications of Johnson-Mehl diagrams in molecular biology" in der Arbeitsgruppe bei Prof. Caflisch, Inst. f. Biochemie, Universität Zürich, Schweiz, (14. März 1997).
    - "Applications of Johnson-Mehl diagrams in molecular biology" in der Arbeitsgruppe bei Prof. Froemmel, Inst. f. Biochemie, Charite, Humboldt-Universität Berlin, Deutschland (21. März 1997).

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

J. BLÖMER
- Berechnungskomplexität kombinatorischer Probleme (Vorlesung und Übungen WS 96/97)
- Algorithmen in der Zahlentheorie (Vorlesung und Übungen SS 97)

B. VON STENGEL
- Logik (Vorlesung und Übungen WS 96/97)

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


Organisation von wissenschaftlichen Veranstaltungen

- Equinoctial School "Geometry and Computation", 15.-26. September 1997.


Diplomarbeiten


Sonstiges

A. ANDREZEJAK
- Mitglied der Hochschulversammlung der ETH Zürich (Vertreter des Mittelbaus (AVETH)) (seit August 1997).
- Assistent für die Vorlesung Informatik I der Abt. IIIb im WS 96/97.
- Assistent für die Vorlesung Theoretische Informatik der Abteilung IIIc im SS 97.

J. BLÖMER
- Gutachter für Zeitschriften: Algorithmica, IEEE Transactions on Information Theory.

B. GÄRTNER
- Konferenzbesuch: 13th ACM Symposium and Workshop on Geometric Computing, Nice, Frankreich, 2.-6. Juni 1997.
- Konferenzbesuch: Seminar: Polytopes and Optimization, Oberwohlfach, Deutschland, 16.-22. November 1997.

J. GIESEN
- Assistent für die Vorlesung Informatik I der Abt. IIIb im WS 96/97.
- Assistent für die Vorlesung Theoretische Informatik der Abt. IIIc im SS 97.

M. Hoffmann
- Assistent für die Vorlesung.

L. KETTNER
- Gutachter für die internationale Konferenz Computer Graphics Internationl.
- Mitarbeit am ESPRIT IV LTR Project No. 21957 (CGAL).
- Konferenzbesuch: Workshop on Geometric Computing, INRIA Sophia Antipolis, Frankreich, 2.-3. Juni 1997.
- Konferenzbesuch: 13th ACM Symposium on Computational Geometry, Nice, Frankreich, 4.-6. Juni 1997.
- Betreuung der Equinoctial School: Geometry and Computation, ETH Zürich, Schweiz, 15.-26. September 1997.
- Chefassistent für die Vorlesung Informatik I der Abt. IIIb im WS 96/97.
- Assistent für die Vorlesung Geometrisches Rechnen der Abt. IIIc SS 97.

B. VON STENGEL
- Gutachter für Zeitschriften: Mathematical Social Sciences, Mathematics of Operations Research.
- Gutachter für Konferenzen: IEEE Symposium on Multiple-Valued Logic 1998.
- Rezensent für Mathematical Reviews.

E. WELZL
- Mitglied des Editorial Boards von

- Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
- Mitglied der Computational Geometry Steering Committee (Vorsitz: Prof. Joseph S. B. Mitchell, SUNY Stony Brook, USA)(bis Juni 1997).
- Vorsitzender des Gödel Prize Committee (SIGACT ACM und EATCS).
- Mitglied des Programmkommitees Eurographics '97, (Budapest, Ungarn, 4.-8. September 97).
- Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Effiziente Algorithmen für Diskrete Probleme und ihre Anwendungen" der Deutschen Forschungsgemeinschaft (DFG).
- Herausgeber eines Sonderbandes von Computational Geometry - Theory and Application 7: 5-6 (1997).
- Mitglied der Dozentenkommission der ETH Zürich.

H.-M. Will
- Assistent für die Vorlesung Informatik I für die Abt. IIIb im WS 96/97.
- Assistent für die Vorlesung Theoretische Informatik für die Abteilung IIIc im SS 97.
- Frauenförderung im SS 97.



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