Geometric medians

DOI10.1016/0012-365X(92)90658-3MaRDI QIDQ1201233zbMATH OpenOpenAlexFDO

Authors William Steiger, A. Wigderson, Joseph (Yossi) Gil

Publication date 17 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90658-3

zbMATH Keywords

medianpoint depthsorting

Mathematics Subject Classification ID

Inequalities and extremum problems in real or complex geometry (51M16) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

The authors investigate measures that state how deep a point of a finite set \(S\subset\mathbb{R}^ d\) stick inside the set. A point of \(S\) is called median if there is no deeper point in \(S\). For \(d>1\) the peel depth, the tukey depth, the simplicial depth and the box depth are quite different while the definitions coincide for \(d=1\). Only peel depth and simplicial depth are invariant under linear transformations. Furthermore are considered: the range of variation of the depth of each median, the so called breakdown point in each case of the medians, an \(O(n^ d)\)-time algorithm to compute the simplicial median for \(d=2\) and \(d=3\). The paper finishes with a number of problems.

Recommendations

• On Combinatorial Depth Measures
• The projection median of a set of points in \({\mathbb{R}}^{d}\)
• On a notion of simplicial depth
• The multivariate L ₁ -median and associated data depth
• On a notion of data depth based on random simplices

Cites work

• A generalization of Caratheodory's theorem
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Convex hulls of finite sets of points in two and three dimensions
• scientific article; zbMATH DE number 3121295 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• On k-Hulls and Related Problems
• On a notion of data depth based on random simplices
• On a triangle counting problem
• On the convex layers of a planar set
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• The number of triangles covering the center of an \(n\)-set
• The Ultimate Planar Convex Hull Algorithm?
• Time bounds for selection
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten

Cited in

(24)

• Topological sweep of the complete graph
• The projection median of a set of points
• Multidimensional medians arising from geodesics on graphs
• Algorithms for bivariate medians and a Fermat-Torricelli problem for lines.
• The complexity of hyperplane depth in the plane
• Multivariate analysis by data depth: Descriptive statistics, graphics and inference. (With discussions and rejoinder)
• On Liu's simplicial depth and Randles' interdirections
• Computing colourful simplicial depth and Median in \(\mathbb{R}_2\)
• Geometrical properties of the mean-median map
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
• Enumerating trichromatic triangles containing the origin in linear time
• Algorithms for colourful simplicial depth and medians in the plane
• On a notion of simplicial depth
• scientific article; zbMATH DE number 472925 (Why is no real title available?)
• \(\beta\)-skeleton depth functions and medians
• Geometric median and its application in the identification of multiple outliers
• Medians and means in Finsler geometry
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Finding simplices containing the origin in two and three dimensions
• Optimal algorithms for geometric centers and depth
• The complexity of order type isomorphism
• Oja centers and centers of gravity
• Médianes vectorielles. (Vectorial medians)
• Approximate centerpoints with proofs

This page was built for publication: Geometric medians

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