License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.28
URN: urn:nbn:de:0030-drops-104329
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10432/
Go to the corresponding LIPIcs Volume Portal

Driemel, Anne ; Phillips, Jeff M. ; Psarros, Ioannis

The VC Dimension of Metric Balls Under Fréchet and Hausdorff Distances

pdf-format:
LIPIcs-SoCG-2019-28.pdf (0.7 MB)

Abstract

The Vapnik-Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computational tasks such as classification, range counting, and density estimation through the use of sampling bounds. We analyze set systems where the ground set X is a set of polygonal curves in R^d and the sets {R} are metric balls defined by curve similarity metrics, such as the Fréchet distance and the Hausdorff distance, as well as their discrete counterparts. We derive upper and lower bounds on the VC dimension that imply useful sampling bounds in the setting that the number of curves is large, but the complexity of the individual curves is small. Our upper bounds are either near-quadratic or near-linear in the complexity of the curves that define the ranges and they are logarithmic in the complexity of the curves that define the ground set.

BibTeX - Entry

@InProceedings{driemel_et_al:LIPIcs:2019:10432,
  author =	{Anne Driemel and Jeff M. Phillips and Ioannis Psarros},
  title =	{{The VC Dimension of Metric Balls Under Fr{\'e}chet and Hausdorff Distances}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10432},
  URN =		{urn:nbn:de:0030-drops-104329},
  doi =		{10.4230/LIPIcs.SoCG.2019.28},
  annote =	{Keywords: VC dimension, Fr{\'e}chet distance, Hausdorff distance}
}

Keywords: VC dimension, Fréchet distance, Hausdorff distance
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI