Summary: PARTITIONING AND GEOMETRIC EMBBDDING OF RANGE SPACES
OF FINITE VAPNIK-CHBRVONBNKIS DIMENSION
i . fntroduction and statement of results.
Permissionto copy without feeall or part of this material is grantedprovided
that the copiesare not madeor distributed for direct commercialadvantage,
the ACM copyright notice and the title of the publication and its dateappear,
and notice isgiven that copying is by permissionof the Association for Com-
puting Machinery. To copy otherwise, or to republish,requiresa feeand/or
0 1987 ACMO-89791-231-4/87/GUG6/0331754
dimensional. ~ucl,idean space?
finite A cr X it produces a data structure
for A such thet., for all r in R, I:(fl(Jo !
xcrnA) can be computed in time at most
In our results we will be mainly con-
crerncd with the First two components of a
I-nngc sr:src:h problem.
Definition. A range space S is a pair