2015/10/30 by Jeff M. Phillips, Yan Zheng, Phillips, Jeff M. +1
Computer Science · Mathematics · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.1510.09123
openalex publication_date 2015/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ε -nets and ε -samples (aka ε-approximations). We characterize when size bounds for ε -samples on kernels can be extended to these more general smoothed range spaces. We also describe new generalizations for ε -nets to these range spaces and show when results from binary range spaces can carry over to these smoothed ones.