The VC dimension of metric balls under Fréchet and Hausdorff distances

DOI10.1007/S00454-021-00318-ZMaRDI QIDQ2665263zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1903.03211

zbMATH Keywords

Hausdorff distanceVC dimensionpolygonal curvesFréchet distance

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 1950576 (Why is no real title available?)
• scientific article; zbMATH DE number 7236441 (Why is no real title available?)
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A new upper bound for the VC-dimension of visibility regions
• Almost optimal set covers in finite VC-dimension
• Approximate matching of polygonal shapes
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Clustering time series under the Fréchet distance
• Comparing distributions and shapes using the kernel distance
• FRESH: Fréchet similarity with hashing
• Fast Fréchet queries
• Fast algorithms for approximate Fréchet matching queries in geometric trees
• Geometric approximation algorithms
• Guarding galleries where no point sees a small area.
• Improved bounds on the sample complexity of learning
• Learnability and the Vapnik-Chervonenkis dimension
• Locality-sensitive hashing of curves
• Neural Network Learning
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the complexity of range searching among curves
• On the density of families of sets
• Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
• Quasi-optimal range searching in spaces of finite VC-dimension
• Relative \((p,\varepsilon )\)-approximations in geometry
• Straight-path queries in trajectory data
• Tight lower bounds on the VC-dimension of geometric set systems
• VC dimensions of principal component analysis
• Walking the dog fast in practice: algorithm engineering of the Fréchet distance
• \(\epsilon\)-nets and simplex range queries

Cited in

(4)

• ANN for time series under the Fréchet distance
• Nonparametric Statistical Inference via Metric Distribution Function in Metric Spaces
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• scientific article; zbMATH DE number 7662168 (Why is no real title available?)

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)