I631: Foundation of Computational Geometry
2-1 Quarter, 2011
The first half of the course will be delivered by Tetsuo Asano.
I'll take the second half of the course.
The official language of this course is English.
I'll mainly discuss combinatorial aspects of discrete geometric objects
and algorithms. Such a combinatorial view is also beneficial in high-dimensional geometry, which has a number of applications.
- Order types of points: A combinatorial nature of point sets can be viewed via the concept of order types, and several geometric phenomena can be observed from the combinatorial view.
- Polytopes: This is a central concept, and a combinatorial nature can be viewed via the concept of face lattices. Two representations, the V-representation and the H-representation, are mathematically equivalent but not (known to be) computationally equivalent. We'll look at an algorithm, called the reverse search, to go from one representation to the other.
- Hyperplane arrangements: Another central concept. We'll look at how they are related to particular polytopes, called zonotopes, and also look at how they are related to point sets via duality.
- Envelopes and other substructures of arrangements: Hyperplane arrangements contain abundant information. We'll look at some examples, as envelopes and levels. We'll also discuss how these substructures are related to other concepts such as Voronoi diagrams.
Schedule and Materials
- November 2: Order types of points
- November 7: Polytopes I
- November 9: Polytopes II
- November 14: Hyperplane arrangements I
- November 14 (afternoon): Hyperplane arrangements II
- November 16: Envelopes and Levels I
- (November 21: Cencelled)
- (November 23: Holiday)
- November 28: Envelopes and Levels II
- November 30: Exam