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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 2000

Arbeitsgruppe Prof. Dr. Emo Welzl

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


Mitglieder
  1. Professoren:
    - Fukuda, Komei, Ph.D. (seit 1. September 2000, gemeinsam mit IFOR, ETH, und Dep. Math., EPFL)
    - Welzl, Emo, Dr.

  2. Wissenschaftliche Mitarbeiter:
    - Adamy, Udo
    - Ambühl, Christoph
    - Andrzejak, Artur (bis 31. März 2000)
    - Blömer, Johannes, Dr. (bis 29. Februar 2000)
    - Gärtner, Bernd, Dr.
    - Giesen, Joachim (bis 31. März 2000)
    - Herrmann, Thomas (1. April bis 30. Juni 2000)
    - Hoffmann, Michael
    - John, Matthias
    - Pedroni, Samuele
    - Schönherr, Sven (seit 15. Januar 2000)
    - Solymosi, József (seit 1. Januar 2000, Graduiertenkolleg CGC)
    - Szabo, Tibor, Dr. (seit 1. September 2000, Graduiertenkolleg CGC)
    - Tóth, Csaba Dávid (seit 1. März 2000, Graduiertenkolleg CGC)
    - Tschirschnitz, Falk
    - Wagner, Uli (seit 1. April 2000)

  3. Sekretariat:
    - Böhm, Susanne (ab 1. März bis 31. Oktober 2000)
    - Hefti-Widmer, Franziska (ab 1. November 2000)
    - Krenn, Tanja (bis 29. Februar 2000)

  4. Hilfsassistenten
    - Fischer, Kaspar
    - Wagner, Uli (bis 31. März 2000)


Gäste

PAVEL VALTR, Charles University Prag, Tschechische Republik (19. bis 25. März 2000, und 19. bis 29. Oktober).

MICHA SHARIR, Tel Aviv University, Israel (14. April bis 19. April 2000).
The k-Set Problem.

JÍRI MATOUSEK, Charles University Prag, Tschechische Republik (1. Mai bis 22. Juli 2000).

VAN HA VU, Microsoft Research, Redmond, Washington, USA (3.-7. Juli 2000)
Separation of Random Points.


Drittmittel

Veröffentlichungen und Vorträge

  1. Veröffentlichungen in Zeitschriften (mit Auswahlverfahren)

    H. ALT, S. FELSNER, F. HURTADO, M. NOY, E. WELZL, A class of point sets with few  k-sets, Computational Geometry - Theory and Applications 16 (2000) 95-101.

    R. CORDOVIL, K. FUKUDA, A. GUEDES DE OLIVEIRA, On the cocircuit graph of an oriented matroid, Discrete and Computational Geometry 24 (2000) 257-265.

    J. BLÖMER, Denesting by Bounded Degree Radicals, Algorithmica 28 (2000) 2-15.

    A. FABRI, G.-J. GIEZEMAN, L. KETTNER, ST. SCHIRRA, S. SCHÖNHERR, On the design of CGAL - a computational geometry algorithms library, Software-Practice and Experience 30 (2000) 1167-1202.

    K. FUKUDA, T. TERLAKY, On the Existence of a Short Admissible Pivot Sequence for Feasibility and Linear Optimization Problems, Pure Mathematics and Applications, Mathematics of Optimization 10 (2000) 431-447.

    J. GIESEN, Curve reconstruction, the Traveling Salesman Problem, and Menger's Theorem on Length, Discrete & Computational Geometry 24 (2000) 577-603.

    R. SEIDEL, U. ADAMY, On the exact worst case query complexity of planar point location, Journal of Algorithms 37 (2000) 189-217.


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

    U. ADAMY, J. GIESEN, M. JOHN, New Techniques for Topologically Correct Surface Reconstrucion, Proc. 11th Ann. IEEE Visualization Conf. (Vis) (2000) 373-380.

    CH. AMBÜHL, B. GÄRTNER, B. VON STENGEL, Optimal Projective Algorithms for the List Update Problem, Proc. 27th Ann. International Coll. on Automata, Languages and Programming (ICALP) (2000) 305-316.

    CH. AMBÜHL, Offline List Update is NP-hard, Proc. 8th Ann. European Symp. on Algorithms (ESA) (2000) 42-51.

    CH. AMBÜHL, S. CHAKRABORTY, B. GäRTNER, Computing the LCP of two Point Sets under Approximate Congruence, Proc. 8th Ann. European Symposium on Algorithms (ESA) (2000) 52-63.

    J. BLÖMER, Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices, Proc. 27th Ann. International Coll. on Automata, Languages and Programming (ICALP) (2000) 248-259.

    B. GÄRTNER, Pitfalls in Computing with Pseudorandom Determinants, Proc. 16th Ann. ACM Symp. on Computational Geometry (2000) 148-155.

    B. GÄRTNER, S. SCHÖNHERR, An Efficient, Exact, and Generic Quadratic Programming Solver for Geometric Optimization, Proc. 16th Ann. ACM Symp. on Computational Geometry (2000) 110-118.

    B. GÄRTNER, E. WELZL, Random Sampling in Geometric Optimization: New Insights and Applications, Proc. 16th Ann. ACM Symp. on Computational Geometry (2000) 91-99.

    A. SCHLEICH, S. JOVANOVIC, B. SEDLMAIER, U. WARSCHEWSKE, F. OLTMANNS, S. SCHÖNHERR, W. OGANOVSKY, B. OHNESORGE, T. HOELL, H. SCHERER, Electromagnetic ENT navigation: the NEN system, Proc. 4th Annu. Conf. International Society for Computer Aided Surgery (2000).

    U. WAGNER, E. WELZL, Origin-Embracing Distributions or A Continuous Analogue of the Upper Bound Theorem, Proc. 16th Ann. ACM Symp. on Computational Geometry (2000) 50-56.


  3. Sonstige Veröffentlichungen

    U. ADAMY, J. GIESEN, M. JOHN, The Lambda-Complex and Surface Reconstruction, Proc. 16th European Workshop on Computational Geometry (EuroCG) (2000) 14-17.

    B. BÜELER, A. ENGE, K. FUKUDA, Exact Volume Computation for Convex Polytopes: A Practical Study, in G. Kalai and G. Ziegler, editors, Polytopes - Combinatorics and Computation, DMV-Seminar 29 (2000) 131-154.

    G. BEUTLER, J. KURMANAVICIUS, M. HOFFMANN, R. HUCH, M. BAJKA, Entwicklung eines Nomogramm zur fetalen Gewichtsschätzung (Poster), 24. Dreiländertreffen der Deutschen, österreichischen und Schweizerischen Gesellschaften für Ultraschall in der Medizin, Wien, 7.-9. September 2000.

    A. DUMITRESCU, B. GÄRTNER, S. PEDRONI, E. WELZL, Enumerating Triangulation Paths, Proc. 12th Ann. Canadian Conf. on Computational Geometry (CCCG) (2000) 233-238.

    K. FUKUDA, T.M. LIEBLING, C. LÜTOLF, Extended Convex Hull, Proc. 12th Ann.Canadian Conf. on Computational Geometry (CCCG) (2000) 57-63.

    B. GÄRTNER, E. WELZL, On a Simple Sampling Lemma, Proc. Computing: The Australasian Theory Symp., Electronic Notes in Theoretical Computer Science 31 (2000) 10 pages.

    M. HOFFMANN, Motion Planning amidst Movable Square Blocks: Push-* is NP-hard, Proc. 12th Canadian Conference on Computational Geometry (2000) 205-209.

    U. MONTANARI, J. D. P. ROLIM, E. WELZL, (Eds.), Automata, Languages and Programming, Proc. 27th International Colloquium, ICALP 2000, Lecture Notes in Computer Science 1853 (2000).


  4. Berichte

    B. GÄRTNER, Randomization and Abstraction - Useful Tools for Optimization, BRICS Notes Series NS-00-1, Februar 2000.

    F. TSCHIRSCHNITZ, A Discourse on the Pivot Rules Random-Edge and Random-Facet, Technical Report 348, ETH Zürich, Departement Informatik, Juli 2000.


  5. Vorträge

    U. ADAMY
    - "Surface Reconstruction", Discrete and Algorithmic Geometry, Euroconference in Mathematics on Crete, Anogia, Griechenland (20. August 2000).
    - "New Techniques for Topologically Correct Surface Reconstruction" 11th Ann. IEEE Visualization Conf. (Vis2000), Salt Lake City, Utah, USA, (13. Oktober 2000).

    U. ADAMY/M. JOHN
    - "Surface Reconstruction: Filtering & Optimization", Upper-Rhine-Region Algorithms Workshop 2000, Freiburg, Deutschland (25. Februar 2000).

    C. AMBÜHL
    - "Optimal Projective Algorithms for the List Update Problem", Upper-Rhine-Region Algorithms Workshop 2000, Freiburg, Deutschland (25. Februar 2000).
    - "Optimal Projective Algorithms for the List Update Problem", 27th Ann. International Coll. on Automata, Languages and Programming (ICALP2000), Genf, Schweiz (11. Juli 2000).
    -" Optimal Projective Algorithms for the List Update Problem", Workshop on Efficient Algorithms, Mathematisches Forschungsinstitu, Oberwolfach, Deutschland (7. August 2000).
    - "Offline List Update is NP-hard", 8th Ann. European Symp. on Algorithms (ESA2000), Saarbrücken, Deutschland (5. September 2000)

    K. FUKUDA
    - "Extended Convex Hull", Algorithms Seminar, School of Computer Science, McGill University, Montreal, Kanada (6. September 2000).
    - "Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids", Klee - Grünbaum Geometry Festival, Ein Gev, Israel (12. April 2000).
    - "Every Cubical Zonotope is Uniquely Determined by its Dual Graph", Workshop on Lattices, Polytopes and Tilings, Mathematisches Forschungsinstitut, Oberwolfach, Deutschland (1. März 2000).
    - "Linear Programming Techniques for Polyhedral Computation", Berliner Algorithmen Tag, Berlin, Germany, (18. Februar 2000, eingeladener Vortrag).

    B. GÄRTNER
    - "Randomisierte Optimierung - Neue Hoffnung für ein altes Problem?", Vorlesung des Graduiertenkollegs "Algorithmische Diskrete Mathematik" Berlin, Deutschland (7. Februar 2000).
    - "Random Sampling in Geometric Optimization: New Insights and Applications", 16th ACM Symposium on Computational Geometry, Hong Kong, China (12. Juni 2000).
    - "Pitfalls in Computing with Pseudorandom Determinants", 16th ACM Symposium on Computational Geometry, Hong Kong, China (13. Juni 2000).
    - "N Points and a Line - a Randomized Game in the Plane", Seminar on Discrete and Applicable Mathematics, Department of Mathematics, London School of Economics, London, UK (29. Juni 2000).
    - "(Abstract) Linear Programming on  d-Polytopes with  d+2 Facets", Combinatorics/Geometry Seminar, Department of Mathematics, Washington University, Seattle WA, USA (2. August 2000).
    - "A Simple Sampling Lemma - Analysis and Applications", Department of Computer Science, University of Victoria BC, Kanada (4. August 2000).
    - "Spicing up the Pricing - an Analysis via Generalized LP", International Symposium on Mathematical Programming, Atlanta GA, USA (10. August 2000).
    - "Randomized Methods for Linear Programming", Workshop on Probabilistic Methods in Combinatorial Optimization, BRICS, University of Aarhus, Aarhus, Dänemark (30. August 2000).

    J. GIESEN
    - "The Lambda-Complex and Surface Reconstruction", 16th European Workshop on Computational Geometry (EuroCG2000), Eilat, Israel, (13. März 2000)

    M. HOFFMANN
    - "Covering Points with Rectangles", Upper-Rhine-Region Algorithms Workshop 2000, Freiburg, Deutschland (26. Februar 2000).
    - "Push-* is NP-hard", 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Kanada (17. August 2000).

    S. PEDRONI
    - "Enumerating Triangulation Paths", Upper-Rhine-Region Algorithms Workshop 2000, Freiburg, Deutschland (25. Februar 2000).
    - "Enumerating Triangulation Paths", 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Kanada (18. August 2000).

    S. SCHÖNHERR
    - "An Efficient, Exact, and Generic Quadratic Programming Solver for Geometric Optimization", 16th ACM Symposium on Computational Geometry, Hong Kong, China (12. Juni 2000).
    - "A Quadratic Programming Solver: Geometric Optimisation in CGAL", GALIA Review Meeting, Brüssel, Belgien (19. September 2000).

    J. SOLYMOSI
    - "Structure theorems for systems of segments", Japan Conference on Discrete and Computational Geometry, Tokyo, Japan (22.-25. November 2000, eingeladener Vortrag).
    - "Convex Sets in Concave Position", Intuitive Geometry, Balatonföldvár, Ungarn, (5.-9. Juni 2000).

    CS. D. TÓTH
    - "Illuminating Labyrinths", Intuitive Geometry, Intuitive Geometry, Balatonföldvár, Ungarn, (5.-9. Juni 2000).
    - "Illuminating Labyrinths", ODSA (Optimal Discrete Structures and Algorithms), Rostock, Deutschland, (11.-13. September 2000).
    - "Illuminating both sides of line segments", Japan Conference on Discrete and Computational Geometry, Tokai University, Tokyo, Japan, (22-25 November 2000).

    F. TSCHIRSCHNITZ
    - "Towards New Bounds of Random Edge", Upper-Rhine-Region Algorithms Workshop 2000, Freiburg, Deutschland (25. Februar 2000).

    U. WAGNER
    - "A Continuous Analogue of the Upper Bound Theorem", Intuitive Geometry, Balatonföldvár, Ungarn (5.-9. Juni 2000).
    - "Origin-Embracing Distributions or A Continuous Analogue of the Upper Bound Theorem", 16th ACM Symposium on Computational Geometry, Hong Kong, China (11. Juni 2000).
    - "A Continuous Analogue of the Upper Bound Theorem", Prague Midsummer Combinatorial Workshop VII, Prag, Tschechische Republik (7.-11. August 2000).
    - "A Continuous Analogue of the Upper Bound Theorem", Discrete and Algorithmic Geometry, Euroconference in Mathematics on Crete, Anogia, Griechenland (22. August 2000).

    E. WELZL
    - "On a Simple Sampling Lemma", Computing: The Australasian Theory Symposium (CATS`00), Canberra, Australien (1. Februar 2000, eingeladener Vortrag).
    - "n Punkte und eine Gerade", Kolloquium zu Ehren des 50. Geburtstag von Helmut Alt, Berlin, Deutschland, (9. Mai 2000).
    - "(At most  j)-Facets in 3-Space", Seminar on Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach, Deutschland (31. Mai 2000).
    - "Entering and Leaving  j-Facets, Intuitive Geometry, Balatonföldvár, Ungarn, (5.-9. Juni 2000, eingeladener Vortrag).
    - "n Points and One Line: Analysis of Randomized Games", 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Konstanz, Deutschland, (16. Juni 2000, eingeladener Hauptvortrag).
    -"Algorithms: Curse and Blessing of Sophistication", Latsis Symposium 2000, Computer and Information Technology - The quest for a crystal ball: Where we stand, how did we get here, Zürich, (19. Juni 2000).
    - "n Points and One Line", Discrete and Algorithmic Geometry, Euroconference in Mathematics on Crete, Anogia, Griechenland (22. August 2000).


Vorlesungen und Seminare (WS 99/00 und SS 00)

J. BLÖMER, M. COCHAND, B. GÄRTNER, P. WIDMAYER
- Approximation: Theorie und Algorithmen (Vorlesung und Übung WS 99/00)

B. GÄRTNER, E. WELZL
- Seminar der Theoretischen Informatik (SS 00)
- Rekonstruktion von Flächen (Seminar SS 00)

E. WELZL
- Geometrisches Rechnen (Vorlesung und Übung WS 99/00)
- Theoretische Informatik (Kernfach, Vorlesung und Übung SS 00)
- Algebra II (Vorlesung und Übung SS 00)


Organisation von wissenschaftlichen Veranstaltungen

- Workshop "Evidences of Intractability in Combinatorial Optimization and Counting", ETH Zürich, 5.-7. Juni 2000 (M. Cochand, M. Jerrum, Ch. Papadimitriou, E. Welzl)
- 2nd GALIA Developer Meeting 2000, ETH Zürich, 3.-4. Juli 2000 (B. Gärtner, M. Hoffmann, S. Schönherr).
- Discrete and Algorithmic Geometry, Euroconference in Mathematics on Crete, Anogia, Griechenland, 19.-25. August 2000 (E. Welzl, G.M. Ziegler).
- 3rd GALIA Developer Meeting 2000, ETH Zürich, 18.-19. Dezember 2000 (B. Gärtner, M. Hoffmann, S. Schönherr).


Dissertationen Diplomarbeiten Semesterarbeiten Sonstiges

U. ADAMY
- Blockkurs Geometric Algorithms for the Analysis of Shapes and Patterns, Berlin, 03.-14. 04. 2000 (H. Alt und G. Rote)
- Summer School on Shape in Computer Vision and Graphics ETH Z\uuml;rich, 06.-08. September 2000 (M. Gross, B. Schiele, G. Szekely, L.V. Gool, M. Pollefeys)
- Ü-Betr. Logik (WS99/00; 2x), Theoretische Informatik (Grundst.; SS00).

C. AMBÜHL
- Fall School on Bioinformatics, Neuseddin, Deutschland, 6.-11. November 2000 (G. Rote)
- Ü-Betr. System Software (WS99/00), Informatik II (SS00).

B. GÄRTNER
- Präsentation "Wahlfach Informatik und Algorithmik", Informationsveranstaltung für Studierende der Mathematik und Physik, veranstaltet vom VPM, 16. Mai 2000.
- Ü-Betr. Theoretische Informatik (Kernfach; SS00; 2x).

J. GIESEN
- Ü-Betr. Informatik I (Abt IX; WS99/00). Seminar-Betr. TI (WS99/00).

M. HOFFMANN
- Teilnahme am 1. GALIA Developer Meeting 2000, Tel-Aviv, Israel, 7.-9. März 2000.
- Teilnahme am 16. European Workshop on Computational Geometry, Eilat, Israel, 13.-15. März 2000.
- Ü-Betr. Geometrisches Rechnen (WS99/00), Informatik II (SS99/00).
- Begutachtungen für ICALP, ESA, und STACS.

M. JOHN
- Blockkurs Geometric Algorithms for the Analysis of Shapes and Patterns, Berlin, 03.-14. 04. 2000 (H. Alt und G. Rote)
- Summer School on Shape in Computer Vision and Graphics ETH Z\uuml;rich, 06.-08. 09. 2000 (M. Gross, B. Schiele, G. Szekely, L.V. Gool, M. Pollefeys)
- Fall School on Bioinformatics, Neuseddin, Deutschland, 6.-11. November 2000 (G. Rote)
- Ü-Betr. Logik (WS99/00), Theoretische Informatik (Grundst.; SS00).

S. PEDRONI
- Ü-Betr. Informatik I (Abt IX; WS99/00), Informatik I (D-MAVT; SS00).

S. SCHÖNHERR
- Fall School on Bioinformatics, Neuseddin, Deutschland, 6.-11. November 2000 (G. Rote)
- Blockkurs Algorithmische Grundlagen Geographischer Informationssysteme, ETH Zürich, 10.-14. April 2000 (G. Neyer, M. Norrie, C. Parent, J.-R. Sack, B. Seeger, C. Stamm, P. Widmayer)
- Design und Realisierung der WWW-Seiten des Graduiertenkollegs "Combinatorics, Geometry, and Computation".
- Teilnahme am 2. und 3. GALIA Developer Meeting 2000, Zürich, 3.-4. Juli 2000 und 18.-19. Dezember 2000.

J. SOLYMOSI
- Blockkurs Geometric Algorithms for the Analysis of Shapes and Patterns, Berlin, 03.-14. 04. 2000 (H. Alt und G. Rote)
- Block course: Randomized Algorithms, Zurich, 23. Oktober - 24. November 2000 (E. Welzl)

C. D. TÓTH
- Blockkurs Geometric Algorithms for the Analysis of Shapes and Patterns, Berlin, 03.-14. 04. 2000 (H. Alt und G. Rote)
- Block course: Randomized Algorithms, Zurich, 23. Oktober - 24. November 2000 (E. Welzl)

F. TSCHIRSCHNITZ
- Fall School on Bioinformatics, Neuseddin, Deutschland, 6.-11. November 2000 (G. Rote)
- Mittelbauvertreter D-INFK.
- Ü-Betr. Informatik I (Abt IX; WS99/00), Informatik II (SS00).

U. WAGNER
- Überblicksvortrag zu "Cinderella" für das Schnupperstudium im Rahmen der Frauenförderung, (7. September 2000)
- Block course: Randomized Algorithms, Zurich, 23. Oktober - 24. November 2000 (E. Welzl)
- Ü-Betr. Theoretische Informatik (Kernfach; SS00; 2x).

E. WELZL
- Mitglied der Editorial Boards von

- Vorsitzender des Programmkomitees

- Mitglied der Programmkomitees

- Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
- Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Effiziente Algorithmen für Diskrete Probleme und ihre Anwendungen" der Deutschen Forschungsgemeinschaft (DFG).
- Mitglied der Konferenz der Dozenten der ETH Zürich.
- Mitglied des Dozentenausschuss der ETH Zürich.
- Sprecher des Graduiertenkollegs `Combinatorics, Geometry, and Computation' (Standort Zürich).- Mitglied der Kommission Pflichtwahlfach der ETH Zürich.
- Korreferent bei Promotion Stege, Ulrike, "Resolving Conflicts in Problems from Computational Biology", ETH Zürich, Doktorprüfung: 3. März 2000.


Emo Welzl - January 16, 2001