On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
From MaRDI portal
Publication:3837388
DOI10.1006/jagm.1996.0060zbMath0864.68040OpenAlexW4385965835MaRDI QIDQ3837388
Ji{ří} Matoušek, Bernard Chazelle
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
Related Items (48)
Improved algorithms for the bichromatic two-center problem for pairs of points ⋮ APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k ⋮ Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls ⋮ Minimum enclosing circle of a set of fixed points and a mobile point ⋮ Covering points by disjoint boxes with outliers ⋮ Near-optimal coresets of kernel density estimates ⋮ Approximate aggregation for tracking quantiles and range countings in wireless sensor networks ⋮ Simple linear time algorithms for piercing pairwise intersecting disks ⋮ A Filtering Heuristic for the Computation of Minimum-Volume Enclosing Ellipsoids ⋮ Stabbing pairwise intersecting disks by four points ⋮ Approximate Polytope Membership Queries ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Ham-sandwich cuts for abstract order types ⋮ The 2-center problem in three dimensions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS ⋮ Unnamed Item ⋮ Unique sink orientations of grids ⋮ Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function ⋮ Violator spaces: Structure and algorithms ⋮ A streaming algorithm for 2-center with outliers in high dimensions ⋮ Optimizing squares covering a set of points ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Bichromatic 2-center of pairs of points ⋮ Largest bounding box, smallest diameter, and related problems on imprecise points ⋮ Approximate range searching: The absolute model ⋮ Unnamed Item ⋮ Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex Constraints ⋮ Stabbing pairwise intersecting disks by five points ⋮ Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point ⋮ Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions ⋮ Unnamed Item ⋮ Deterministic Algorithms for Unique Sink Orientations of Grids ⋮ A fully polynomial time approximation scheme for the smallest diameter of imprecise points ⋮ APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING ⋮ Subsampling in Smoothed Range Spaces ⋮ The complexity of optimization on grids ⋮ Improved algorithms via approximations of probability distributions ⋮ Computing a geodesic two-center of points in a simple polygon ⋮ Economical Delone Sets for Approximating Convex Bodies ⋮ Streaming algorithms for extent problems in high dimensions ⋮ On the planar two-center problem and circular hulls
This page was built for publication: On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
