Efficient algorithms for maximum regression depth

DOI10.1007/s00454-007-9046-6zbMath1161.62043OpenAlexW2148269135WikidataQ56970327 ScholiaQ56970327MaRDI QIDQ938312

Joseph S. B. Mitchell, Bettina Speckmann, Micha Sharir, Marc J. van Kreveld, Jack Scott Snoeyink, Peter J. Rousseeuw

Publication date: 19 August 2008

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-007-9046-6

zbMATH Keywords

undirected depth

Mathematics Subject Classification ID

Optimal statistical designs (62K05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Robust parameter designs (62K25)

Related Items

Online signal extraction by robust linear regression, The complexity of hyperplane depth in the plane, Robust regression quantiles., The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Optimal Algorithms for Geometric Centers and Depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal slope selection via expanders
• Halfspace range search: An algorithmic application of k-sets
• On `\(k\)-sets' in the plane
• A simple algorithm for determining the envelope of a set of lines
• Randomized optimal algorithm for slope selection
• Cutting hyperplanes for divide-and-conquer
• The catline for deep regression
• Halfspace depth and regression depth characterize the empirical distribution
• Depth in an arrangement of hyperplanes
• \(k\)-sets and random hulls
• Computing depth contours of bivariate point clouds
• Improved bounds for planar \(k\)-sets and related problems
• Optimal slope selection via cuttings
• The complexity of hyperplane depth in the plane
• Robustness of deepest regression
• High-dimensional computation of the deepest location.
• The deepest regression method
• The exact fitting problem in higher dimensions
• Regression depth and center points.
• Dynamic planar convex hull operations in near-logarithmic amortized time
• Constructing Arrangements of Lines and Hyperplanes with Applications
• An Optimal-Time Algorithm for Slope Selection
• On the Zone Theorem for Hyperplane Arrangements
• Regression Depth
• On Envelopes of Arrangements of Lines
• Point sets with many \(k\)-sets
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION