Vapnik-Chervonenkis Dimension and (Pseudo-)Hyperplane Arrangements 


Bernd Gärtner, Emo Welzl
Institut für Informatik
Freie Universität Berlin
email: gaertner@inf.fu-berlin.de
Report B 93-07
June 93 

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-93-07.ps.gz
An arrangement of oriented pseudohyperplanes in Euclidean $d$-space defines on the 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 complete}, and we show that the number of ranges $r \in R$ for which also $X-r \in R$, determines whether a complete 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.\\ \noindent {\bf Keywords}: VC-dimension, hyperplane arrangements, oriented matroids, pseudohyperplane ar\-range\-ments.