Abstract
An arrangement of oriented pseudohyperplanes in affined-space defines on its setX of pseudohyperplanes a set system (or range space) (X, ℛ), ℛ ⊑ 2x of VC-dimensiond in a natural way: to every cellc in the arrangement assign the subset of pseudohyperplanes havingc on their positive side, and let ℛ be the collection of all these subsets. We investigate and characterize the range spaces corresponding tosimple arrangements of pseudohyperplanes in this way; such range spaces are calledpseudogeometric, and they have the property that the cardinality of ℛ is maximum for the given VC-dimension. In general, such range spaces are calledmaximum, and we show that the number of rangesR∈ℛ for whichX - R∈ℛ also, 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 uniforom oriented matroids: a range space (X, ℛ) naturally corresponds to a uniform oriented matroid of rank |X|—d if and only if its VC-dimension isd,R∈ℛ impliesX - R∈ℛ, and |ℛ| is maximum under these conditions.
Article PDF
Similar content being viewed by others
References
M. Anthony and N. Biggs,Conputational Learning Theory, Cambridge Tracts in Theoretical Computer Science, Vol. 30, Cambridge University Press, Cambridge, 1992.
N. Alon, D. Haussler, and E. Welzl, Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension,Proc. 3rd Ann. ACM Symp. on Computational Geometry, 1987, pp. 331–340.
K. S. Alexander, Probability-inequalities for empirical processes and a law of the iterated logarithm,Ann. Probab. 6 (1984), 1041–1067.
P. Assouad, Densité et dimension,Ann. Inst. Fourier 33 (1983), 233–282.
E. Baum and D. Haussler, What size net gives valid generalization?,Neural Comput. 1 (1989), 151–160.
W. Bienia and R. Cordovil, An axiomatic of non-Radon partitions of oriented matroids,European J. Combin. 8 (1987), 1–4.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth, Learnability and the Vapnik-Chervonenkis dimension,J. Assoc. Comput. Mach. 36 (1989), 929–965.
R. G. Bland and M. Las Vergnas, Orientability of matroids,J. Combin. Theory Ser. B 24 (1978), 94–123.
A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler,Oriented matroids, Encyclopedia of Mathematics, Cambridge University Press, Cambridge, 1992.
B. Chazelle and J. Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension,Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1993, pp. 281–290.
B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension,Discrete Comput. Geom. 4 (1989), 467–489.
D. Z. Djoković, Distance-preserving subgraphs of hypercubes,J. Combin. Theory Ser. B 14 (1973), 263–267.
G. Ding, P. Seymour, and P. Winkler, Bounding the vertex cover number of a hypergraph,Combinatorica 14 (1994), 23–34.
R. M. Dudley, Central limit theorems for empirical measures,Ann. Probab. 6 (1978), 899–929.
R. M. Dudley,A Course on Empirical Measures, Lecture Notes in Mathematics, Vol. 1097, Springer-Verlag, Berlin, 1984, pp. 2–142.
R. M. Dudley, The structure of some Vapnik-Chervonenkis classes,Proc. Berkeley Conference in Honor of Jerzy Neyman and Jack Kiefer, Vol. II (L. M. Le Cam and R. A. Olshen, eds.), Wadsworth, New York, 1985, pp. 495–507.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1987.
J. Edmonds and A. Mandel, Topology of Oriented Matroids, Ph.D. thesis, University of Waterloo, Ontario (1981).
S. Floyd, On Space-Bounded Learning and the Vapnik-Chervonenkis Dimension, Ph.D. thesis, University of California at Berkeley (1989).
J. Folkman and J. Lawrence, Oriented matroids,J. Combin. Theory Ser. B 25 (1978), 199–236.
P. Goldberg and M. Jerrum, Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers,Proc. Sixth Annual ACM Conference on Computational Learning Theory, 1993, pp. 361–369.
J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane,J. Combin. Theory Ser. A 29 (1980), 220–235.
J. E. Goodman and R. Pollack, Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines,J. Combin. Theory Ser. A 29 (1980), 385–390.
J. E. Goodman and R. Pollack, Three points do not determine a (pseudo-)plane,J. Combin. Theory Ser. A 31 (1981), 215–218.
B. Grünbaum,Convex Polytopes, Series in Pure and Applied Mathematics, Vol. 16, Interscience, New York, 1967.
B. Grünbaum,Arrangements and Spreads, CBMS Regional Conference Series in Mathematics, No. 10, American Mathematical Society, Providence, RI, 1972.
E. Giné and J. Zinn, Some limit theorems for empirical processes,Ann. Probab. 12 (1984), 929–989.
K. Handa, A characterization of oriented matroids in terms of topes,European J. Combin. 11 (1990), 41–45.
D. Haussler, Sphere-packing numbers for subsets of the booleann-cube with bounded Vapnik-Chervonenkis dimension,J. Combin. Theory Ser. A, to appear.
D. Haussler, M. Kearns, and R. Schapire, Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension,Machine Learning 14 (1994) 84–114.
D. Haussler and E. Welzl, ε-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127–151.
J. Karlander, A characterization of affine sign vector systems, Preprint, KTH, Stockholm (1992).
J. Komlós, J. Pach, and G. Woeginger, Almost tight bounds for ε-nets,Discrete Comput. Geom. 7 (1992), 163–173.
M. Las Vergnas, Oriented matroids as signed geometries real in corank 2, inFinite and Infinite Sets (Proc. 6th Hungarian Combinatorial Conf., Eger, 1981), North-Holland, Amsterdam, 1984, pp. 555–565.
J. Lawrence, Lopsided sets and orthant-intersection by convex sets,Pacific J. Math. 104(1) (1983), 155–173.
F. Levi, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade,Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig 78 (1926), 256–267.
N. Linial, Y. Mansour, and R. L. Rivest, Results on learnability and the Vapnik-Chervonenkis dimension,Inform. Comput. 90 (1991), 33–49.
J. Matoušek, Approximations and optimal geometric divide and conquer,Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991, pp. 506–511.
J. Matoušek, E. Welzl, and L. Wernisch, Discrepancy and approximations for bounded VC-dimension,Combinatorica 13 (1993), 455–466.
B. K. Natarajan,Machine Learning: A Theoretical Approach, Morgan Kaufmann, San Mateo, CA, 1991.
J. Pearl, Capacity and error estimates for Boolean classifiers with limited complexity,IEEE Trans. Pattern Anal. Mach. Intell. 1 (1979), 350–355.
R. Perrin, Sur le problème des aspect,Bull. Soc. Math. France 10 (1881/82), 103–127.
D. Pollard,Convergence of Stochastic Processes, Springer-Verlag, Berlin 1984.
D. Pollard,Empirical Processes: Theory and Applications, NSF-CBMS Regional Conference Series in Probability and Statistics, Vol. 2, Institute of Mathematical Statistics and American Statistical Association, Washington, DC, 1990.
J. Richter-Gebert, Oriented matroids with few mutations,Discrete Comput. Geom. 10 (1993), 251–269.
G. Ringel, Teilungen der Ebene durch Geraden oder topologische Geraden,Math. Z. 64 (1956), 79–102.
N. Sauer, On the density of families of sets,J. Combin. Theory Ser. A 13 (1972), 145–147.
S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages,Pacific J. Math. 41 (1972), 247–261.
I. P. da Silva, An axiomatic for the set of maximal vectors of an oriented matroid, based on symmetry properties of the set of vectors, Preprint (1988).
I. P. da Silva, Axioms for maximal vectors of an oriented matroid, a combinatorial characterization for the regions of an arrangement of pseudohyperplanes,European J. Combin., to appear.
J. M. Steele, Existence of sub-matrices with all possible columns,J. Combin. Theory Ser. A 24 (1978), 84–88.
M. Talagrand, Donsker classes of sets,Probab. Theory Related Fields 78 (1988), 169–191.
N. Tomizawa, Theory of acycloid and holometry,RIMS kokyuroku (Graph Theory and Applications) 534 (1984), 91–138 (in Japanese)
V. N. Vapnik,Estimation of Dependences Based on Empirical Data, Springer-Verlag, Berlin, 1982.
V. N. Vapnik and A. Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probability,Theory Probab. Appl. 16 (1971), 264–280.
T. Zaslavsky, Facing up to arrangements: face count formulas for partitions of space by hyperplanes,Mem. Amer. Math. Soc. 1 (1975), no. 154.
Author information
Authors and Affiliations
Additional information
Part of this work was done while the first author was a member of the Graduiertenkolleg “Algorithmische Diskrete Mathematik,” supported by the Deutsche Forschungsgemeinschaft, Grant We 1265/2-1. Part of this work has been supported by the German-Israeli Foundation for Scientific Research and Development (G.I.F.).
Rights and permissions
About this article
Cite this article
Gärtner, B., Welzl, E. Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements. Discrete Comput Geom 12, 399–432 (1994). https://doi.org/10.1007/BF02574389
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02574389