Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
type: Item
instance of: scholarly article
title: Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
zbMATH Open document ID: 0813.52013
DOI: 10.1007/BF02574389
author: B. Gärtner
author: Emo Welzl
published in: Discrete \& Computational Geometry
publication date: 1994-12-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131339
review text: This paper investigates combinatorial abstractions of simple arrangements of hyperplanes in the following way. Let \({\mathcal R}\) be a family of subsets of a finite set \(X\). Then \((X,{\mathcal R})\) is called a range space, and the maximum cardinality of \(Y\in X\) such that \(\{R\cap Y\mid R\in{\mathcal R}\}= 2^ Y\) is called its VC-dimension. It turns out that the range space \((X,{\mathcal R})\) of VC-dimension \(d\) with maximum cardinality of \({\mathcal R}\) corresponds to the set of (full dimensional) cells of a simple arrangement of oriented pseudo-hyperplanes in affine \(d\)-space if and only if the number of ranges \(R\in {\mathcal R}\) for which also \(X-R\in {\mathcal R}\) has a certain value. Such range spaces are called pseudogeometric and are also characterized in different ways. The maximum range spaces of given VC-dimension with \(X-R\in {\mathcal R}\) for each \(R\in {\mathcal R}\) correspond to simple arrangements of pseudohemispheres (i.e. uniform oriented matroids). Thus a new approach to oriented matroids is obtained.
reviewed by: Johann Linhart
Mathematics Subject Classification ID: 52B40
Mathematics Subject Classification ID: 52C35
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 698616
zbMATH Keywords: range spaces
zbMATH Keywords: arrangements of hyperplanes
zbMATH Keywords: VC-dimension
zbMATH Keywords: oriented matroids
Wikidata QID: Q54309388
MaRDI profile type: Publication
cites work: Q4004178
cites work: Probability inequalities for empirical processes and a law of the iterated logarithm
cites work: Density and dimension
cites work: An axiomatic of non-Radon partitions of oriented matroids
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Orientability of matroids
cites work: Q3140430
cites work: Quasi-optimal range searching in spaces of finite VC-dimension
cites work: Distance-preserving subgraphs of hypercubes
cites work: Bounding the vertex cover number of a hypergraph
cites work: Central limit theorems for empirical measures
cites work: Q3217346
cites work: Q3772828
cites work: Q4013552
cites work: Oriented matroids
cites work: On the combinatorial classification of nondegenerate configurations in the plane
cites work: Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
cites work: Three points do not determine a (pseudo-) plane
cites work: Q5547252
cites work: Q5663020
cites work: Some limit theorems for empirical processes (with discussion)
cites work: A characterization of oriented matroids in terms of topes
cites work: Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Almost tight bounds for \(\epsilon\)-nets
cites work: Q3682500
cites work: Lopsided sets and orthant-intersection by convex sets
cites work: Results on learnability and the Vapnik-Chervonenkis dimension
cites work: Discrepancy and approximations for bounded VC-dimension
cites work: Capacity and Error Estimates for Boolean Classifiers with Limited Complexity
cites work: Convergence of stochastic processes
cites work: Q4001821
cites work: Oriented matroids with few mutations
cites work: Teilungen der Ebenen durch Geraden oder topologische Geraden
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
cites work: Axioms for maximal vectors of an oriented matroid: A combinatorial characterization of the regions determined by an arrangement of pseudohyperplanes
cites work: Existence of submatrices with all possible columns
cites work: Donsker classes of sets
cites work: Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
OpenAlex ID: W1967689501
DBLP publication ID: journals/dcg/GartnerW94
description: scientific article; zbMATH DE number 698616