# I631: Foundation of Computational Geometry

2-1 Quarter, 2011

Yoshio Okamoto

The first half of the course will be delivered by Tetsuo Asano.
I'll take the second half of the course.

## Language

The official language of this course is English.
## Topic

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

[Teaching Top]

okamotoy@uec.ac.jp