The VC dimension of metric balls under Fréchet and Hausdorff distances
DOI10.1007/S00454-021-00318-ZOpenAlexW3191148826MaRDI QIDQ2665263FDOQ2665263
Authors: Anne Driemel, André Nusser, Jeff M. Phillips, Ioannis Psarros 
Publication date: 18 November 2021
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.03211
Recommendations
- The VC dimension of metric balls under Fréchet and Hausdorff distances
- Tight lower bounds on the VC-dimension of geometric set systems
- The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension
- VC‐dimension on manifolds: a first approach
- Probabilistic embeddings of the Fréchet distance
General topics of discrete mathematics in relation to computer science (68R01) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) General topics in the theory of data (68P01)
Cites Work
- Comparing distributions and shapes using the kernel distance
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Learnability and the Vapnik-Chervonenkis dimension
- \(\epsilon\)-nets and simplex range queries
- Almost optimal set covers in finite VC-dimension
- Neural Network Learning
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- Geometric approximation algorithms
- Walking the dog fast in practice: algorithm engineering of the Fréchet distance
- Guarding galleries where no point sees a small area.
- A new upper bound for the VC-dimension of visibility regions
- Quasi-optimal range searching in spaces of finite VC-dimension
- Approximate matching of polygonal shapes
- Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
- Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
- Relative \((p,\varepsilon )\)-approximations in geometry
- VC dimensions of principal component analysis
- Improved bounds on the sample complexity of learning
- Clustering time series under the Fréchet distance
- Fast Fréchet queries
- Fast algorithms for approximate Fréchet matching queries in geometric trees
- Locality-sensitive hashing of curves
- On the complexity of range searching among curves
- Title not available (Why is that?)
- Tight lower bounds on the VC-dimension of geometric set systems
- FRESH: Fréchet similarity with hashing
- Straight-path queries in trajectory data
Cited In (4)
This page was built for publication: The VC dimension of metric balls under Fréchet and Hausdorff distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2665263)
