On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

DOI10.1006/jagm.1996.0060zbMath0864.68040MaRDI QIDQ3837388

Bernard Chazelle, Ji{ří} Matoušek

Publication date: 8 July 1997

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1996.0060

zbMATH Keywords

Clarkson's randomized algorithm

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

Related Items

APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS, THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS, Minimum enclosing circle of a set of fixed points and a mobile point, Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs, Covering points by disjoint boxes with outliers, Approximate aggregation for tracking quantiles and range countings in wireless sensor networks, Unique sink orientations of grids, Violator spaces: Structure and algorithms, Improved algorithms via approximations of probability distributions, The 2-center problem in three dimensions, Bichromatic 2-center of pairs of points, Largest bounding box, smallest diameter, and related problems on imprecise points, Approximate range searching: The absolute model, Streaming algorithms for extent problems in high dimensions, QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS, Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex Constraints, Deterministic Algorithms for Unique Sink Orientations of Grids, Subsampling in Smoothed Range Spaces, COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k, Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls, Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point, APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING