Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

We investigate the combinatorial structure of linear programs on simple $d$-polytopes with $d+2$ facets. These can be encoded by {\em admissible} grid orientations. Admissible grid orientations are also obtained through orientation properties of a planar point configuration or by the dual line arrangement. The point configuration and the polytope corresponding to the same grid are related through an extended Gale transform. The class of admissible grid orientations is shown to contain non-realizable examples, i.e., there are admissible grid orientations which cannot be obtained from a polytope or a point configuration. It is shown, however, that every admissible grid orientation is induced by an arrangement of pseudolines. This later result is used to prove several nontrivial facts about admissible grid orientations.