Product Range Spaces, Sensitive Sampling, and Derandomization

DOI10.1137/S0097539796260321MaRDI QIDQ4268808zbMATH OpenOpenAlexFDO

Authors 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 hulldeterministic algorithmoptimal

Mathematics Subject Classification ID

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

Recommendations

• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• An optimal convex hull algorithm in any fixed dimension
• Approximations and optimal geometric divide-and-conquer

Cited in

(11)

• Almost optimal set covers in finite VC-dimension
• The \(\varepsilon\)-\(t\)-net problem
• Subquadratic algorithms for algebraic 3SUM
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Distribution-sensitive bounds on relative approximations of geometric ranges
• An efficient algorithm for the three-dimensional diameter problem
• Approximating length-restricted means under dynamic time warping
• Relative (p, )-approximations in geometry
• Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
• Hitting and covering affine families of convex polyhedra, with applications to robust optimization

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

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