Small-size relative ( p ,ε)-approximations for well-behaved range spaces

DOI10.1145/2462356.2462363MaRDI QIDQ5174483zbMATH OpenOpenAlexFDO

Authors Esther Ezra

Publication date 17 February 2015

Published in Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

Lovász local lemmarelative approximationswell-behaved range spaces

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We present improved upper bounds for the size of relative (p,Epsilon)-approximation for range spaces with the following property: For any (finite) range space projected onto (that is, restricted to) a ground set of size n and for any parameter 1 <= k <= n, the number of ranges of size at most k is only nearly-linear in n and polynomial in k. Such range spaces are called "well behaved". Our bound is an improvement over the bound O(log{(1/p)/eps^2 p) introduced by Li etal. for the general case (where this bound has been shown to be tight in the worst case), when p << Epsilon. We also show that such small size relative (p,Epsilon)-approximations can be constructed in expected polynomial time. Our bound also has an interesting interpretation in the context of "p-nets": As observed by Har-Peled and Sharir, p-nets are special cases of relative (p,Epsilon)-approximations. Specifically, when Epsilon is a constant smaller than 1, their analysis implies that there are p-nets of size O(log{(1/p)}/p) that are emph{also} relative approximations. In this context our construction significantly improves this bound for well-behaved range spaces. Despite the progress in the theory of p-nets and the existence of improved bounds corresponding to the cases that we study, these bounds do not necessarily guarantee a bounded relative error. Lastly, we present several geometric scenarios of well-behaved range spaces, and show the resulting bound for each of these cases obtained as a consequence of our analysis. In particular, when Epsilon is a constant smaller than 1, our bound for points and axis-parallel boxes in two and three dimensions, as well as points and "fat" triangles in the plane, matches the optimal bound for p-nets.

Recommendations

• On small compact sets in the spaces L^ p
• Small sets in best approximation theory
• Small Lebesgue spaces and their applications
• On \({\mathcal L}_{p,\lambda}\) spaces for small \(\lambda\)
• Compactness in approximation spaces
• scientific article; zbMATH DE number 95261
• ε–Optimality to approximation in partially ordered spaces
• Best L^p-approximant pair on small intervals
• scientific article; zbMATH DE number 1971076
• scientific article; zbMATH DE number 5905141

Cited in

(5)

• Near-linear algorithms for geometric hitting sets and set covers
• Subsampling in smoothed range spaces
• Geometric Packing under Nonuniform Constraints
• Distribution-sensitive bounds on relative approximations of geometric ranges
• Relative (p, )-approximations in geometry

This page was built for publication: Small-size relative ( p ,ε)-approximations for well-behaved range spaces

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