A proof of the Oja depth conjecture in the plane

作者：Mustafa Nabil H^*; Tiwary Hans Raj; Werner Daniel

来源：Computational Geometry-Theory and Applications, 2014, 47(6): 668-674.

DOI：10.1016/j.comgeo.2013.12.006

• Data depth
• Oja depth
• Centerpoints
• Ray-shooting depth
• Discrete geometry

Given a set P of n points in the plane, the Oja depth of a point x is an element of R-2 is defined to be the sum of the areas of all triangles defined by x and two points from P, normalized with respect to the area of the convex hull of P. The Oja depth of P is the minimum Oja depth of any point in R-2. The Oja depth conjecture states that any set P of n points in the plane has Oja depth at most n(2)/9. This bound would be tight as there are examples where it is not possible to do better. We present a proof of this conjecture. We also improve the previously best bounds for all R-d, d >= 3, via a different, more combinatorial technique.

• 出版日期2014-8