Product Range Spaces, Sensitive Sampling, and Derandomization

DOI10.1137/S0097539796260321zbMath0945.68188OpenAlexW2147017508MaRDI QIDQ4268808

Hervé Brönnimann, Bernard Chazelle, Ji{ří} Matoušek

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796260321

zbMATH Keywords

convex hulloptimaldeterministic algorithm

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Nonnumerical algorithms (68W05)

Related Items (9)

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Almost optimal set covers in finite VC-dimension ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Approximating length-restricted means under dynamic time warping ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ An efficient algorithm for the three-dimensional diameter problem ⋮ Unnamed Item ⋮ RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS

This page was built for publication: Product Range Spaces, Sensitive Sampling, and Derandomization