Optimal Algorithms for Geometric Centers and Depth
From MaRDI portal
Publication:5864667
DOI10.1137/21M1423324OpenAlexW3163968926MaRDI QIDQ5864667
Mitchell Jones, Timothy M. Chan, Sariel Har-Peled
Publication date: 8 June 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.01639
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parametric search made practical
- A polynomial-time algorithm for computing the yolk in fixed dimension
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- Minimum dilation stars
- Efficient algorithms for maximum regression depth
- Fast algorithms for collision and proximity problems involving moving geometric objects
- Small-dimensional linear programming and convex hulls made easy
- Limiting median lines do not suffice to determine the yolk
- Reporting points in halfspaces
- Geometric medians
- Cutting hyperplanes for divide-and-conquer
- On the zone of a surface in a hyperplane arrangement
- Optimal algorithms for some intersection radius problems
- Computing a centerpoint of a finite planar set of points in linear time
- Computing depth contours of bivariate point clouds
- A simpler minimum spanning tree verification algorithm
- Improved bounds for planar \(k\)-sets and related problems
- Algorithms for bivariate medians and a Fermat-Torricelli problem for lines.
- The complexity of hyperplane depth in the plane
- Lower bounds for computing statistical depth.
- Multivariate regression depth
- Geometric applications of a randomized optimization technique
- Applications of random sampling in computational geometry. II
- A subexponential bound for linear programming
- Computing the center region and its variants
- An optimal randomized algorithm for \(d\)-variate zonoid depth
- Shortest path in a polygon using sublinear space
- A Note about the "Nowhere Denseness" of Societies Having an Equilibrium under Majority Rule
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- On k-Hulls and Related Problems
- Linear Programming in Linear Time When the Dimension Is Fixed
- On the Zone Theorem for Hyperplane Arrangements
- New Lower Bounds for Convex Hull Problems in Odd Dimensions
- A randomized linear-time algorithm to find minimum spanning trees
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Faster Algorithms for Computing Plurality Points
- Slowing down sorting networks to obtain faster sorting algorithms
- Linear Optimization Queries
- Setting Parameters by Example
- Algorithms for center and Tverberg points
- Journey to the Center of the Point Set
- A combinatorial bound for linear programming and related problems
- Linear programming queries revisited
- Computing a Center-Transversal Line
- APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
- On lazy randomized incremental construction
- Point sets with many \(k\)-sets
- An optimal deterministic algorithm for computing the diameter of a three-dimensional point set
- Fast Algorithms for Geometric Consensuses
This page was built for publication: Optimal Algorithms for Geometric Centers and Depth
