Subsampling in smoothed range spaces

DOI10.1007/978-3-319-24486-0_15MaRDI QIDQ2835631zbMATH OpenOpenAlexFDO

Authors Jeff M. Phillips, Yan Zheng

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We consider smoothed versions of geometric range spaces, so an element of the ground set (e.g. a point) can be contained in a range with a non-binary value in $[0,1]$. Similar notions have been considered for kernels; we extend them to more general types of ranges. We then consider approximations of these range spaces through $varepsilon$-nets and $varepsilon$-samples (aka $varepsilon$-approximations). We characterize when size bounds for $varepsilon$-samples on kernels can be extended to these more general smoothed range spaces. We also describe new generalizations for $varepsilon$-nets to these range spaces and show when results from binary range spaces can carry over to these smoothed ones.

Recommendations

• -samples for kernels
• Relative (p, )-approximations in geometry
• Small-size relative ( p ,ε)-approximations for well-behaved range spaces
• scientific article; zbMATH DE number 431986
• -nets and simplex range queries

Cites work

• -nets and simplex range queries
• Algorithms for ε-Approximations of Terrains
• Comparing distributions and shapes using the kernel distance
• Concentration of Measure for the Analysis of Randomized Algorithms
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 67607 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• Improved bounds on the sample complexity of learning
• Irregularities of distribution. I
• New existence proofs ε-nets
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On Range Searching in the Group Model and Combinatorial Discrepancy
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Paths, Trees, and Flowers
• Scale-sensitive dimensions, uniform convergence, and learnability
• Small-size -nets for axis-parallel rectangles and boxes
• Tight lower bounds for the size of epsilon-nets
• Tight upper bounds for the discrepancy of half-spaces

Cited in

(2)

• Caratheodory-Tchakaloff Subsampling
• -samples for kernels

This page was built for publication: Subsampling in smoothed range spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835631)