Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

abstract An arrangement of oriented pseudohyperplanes in affine $d$-space defines on its set $X$ of pseudohyperplanes a set system (or range space) $(X,\R)$, $\R\subseteq 2^{X}$ of VC-dimension $d$ in a natural way: to every cell $c$ in the arrangement assign the subset of pseudohyperplanes having $c$ on their positive side, and let $\R$ be the collection of all these subsets. We investigate and characterize the range spaces corresponding to {\em simple} arrangements of pseudohyperplanes in this way; such range spaces are called {\em pseudogeometric}, and they have the property that the cardinality of $\R$ is maximum for the given VC-dimension. In general, such range spaces are called {\em maximum}, and we show that the number of ranges $R \in \R$ for which also $X-R \in \R$, determines whether a maximum range space is pseudogeometric. Two other characterizations go via a simple duality concept and `small' subspaces. The correspondence to arrangements is obtained indirectly via a new characterization of uniform oriented matroids: a range space $(X,\R)$ naturally corresponds to a uniform oriented matroid of rank $|X|-d$ if and only if its VC-dimension is $d$, $R\in \R$ implies $X-R\in \R$ and $|\R|$ is maximum under these conditions.

Back to the publications page