Seminar Geometry: Combinatorics and Algorithms FS16 (263-4203-00L)

Bernd Gärtner,	CAB G32.2,	Tel: 044-632 70 26,	lastname@inf.ethz.ch
Michael Hoffmann,	CAB G33.1,	Tel: 044-632 73 90,	lastname@inf.ethz.ch
Alexander Pilz,	CAB G38,	Tel: 044-632 04 34,	pilza@inf.ethz.ch
Emo Welzl,	CAB G39.2,	Tel: 044-632 73 70,	firstname@inf.ethz.ch

Contents

This seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.

To attend the seminar, some basic knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" or a comparable course is strongly encouraged.

Dates

First meeting: Friday Feb 26th 2016, 13:15, CAB G15.2.

Schedule

• March 18, 13:15-14:00: Saad Arshad
  Jacob E. Goodman, Richard Pollack, On the Combinatorial Classification of Nondegenerate Configurations in the Plane, J. Comb. Theory, Ser. A 29(2): 220-235, 1980. [DOI]
• March 18, 14:15-15:00: Manuel Wettstein
  Jacob E. Goodman, Richard Pollack, A Theorem of Ordered Duality, Geom. Dedic. 12(1):63-74, 1982. [DOI]
• May 13, 13:15-14:00: Patrick Schnider
  Jacob E. Goodman, Richard Pollack, Semispaces of Configurations, Cell Complexes of Arrangements, J. Comb. Theory, Ser. A 37(3): 257-293, 1984. [DOI]
• May 13, 14:15-15:00: Daniel Graf
  Stefan Felsner, Pavel Valtr, Coding and Counting Arrangements of Pseudolines, Discr. Comput. Geom. 46(3): 405-416, 2011. [DOI]

All talks in CAB G15.2.

Topic and Papers

The seminar focuses on Combinatorial Representations of Point Sets: How can the structure of point sets be captured using a discrete representation rather than a representation by coordinates from a continuous domain?

A nice overview is provided by Goodman and Pollack in Allowable Sequences and Order Types in Discrete and Computational Geometry.

• Friedrich Levi, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade, Ber. Verb. Sächs. Gesellsch. Wiss. Leipzig Math. Phys. Kl. 78: 256-267, 1926.
• Jacob E. Goodman and Richard Pollack and Bernd Sturmfels, Coordinate Representation of Order Types Requires Exponential Storage, Proc. 21st ACM Symp. Theory Comput., 405-410, 1989. [DOI]
• Peter W. Shor, Stretchability of Pseudoline Arrangements is NP-hard, in: Applied Geometry and Discrete Mathematics - The Victor Klee Festschrift, American Math. Soc., pp. 531-554, 1991. [PDF]
• Stefan Felsner and Alexander Pilz, Ham-Sandwich Cuts for Abstract Order Types, Proc. 25th Annu. Internat. Sympos. Algorithms Comput., 726-737, 2014. [PDF]
• Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer, Alexander Pilz, Manuel Wettstein, An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings, Proc. 26th Annu. Internat. Sympos. Algorithms Comput., 505-516, 2015. [PDF]

Conditions

The seminar is held in English. Each talk is 45min. plus about 15min. discussion.
Every participant is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes

1. getting an overview of the related literature;
2. understanding and working out the background/motivation: why and where are the questions addressed relevant?
3. understanding the contents of the paper in all details;
4. selecting parts suitable for the presentation;
5. presenting the selected parts in such a way that an audience with some basic background in geometry and graph theory can easily understand and appreciate it.

For more details, please refer to our guidelines for seminar talks. A number of additional related documents from different authors (both in English and German) are linked to from here.

A successful participation in the seminar requires the following:

1. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
2. a satisfactory plenary talk;
3. attendance at all other talks.

---

Last modified: Wed Apr 27 09:55:55 CEST 2016 by Michael Hoffmann.