TY - GEN

T1 - Ray-shooting depth

T2 - 19th Annual European Symposium on Algorithms, ESA 2011

AU - Mustafa, Nabil H.

AU - Ray, Saurabh

AU - Shabbir, Mudassir

PY - 2011

Y1 - 2011

N2 - Over the past several decades, many combinatorial measures have been devised for capturing the statistical data depth of a set of n points in ℝ2. These include Tukey depth [15], Oja depth [12], Simplicial depth [10] and several others. Recently Fox et al. [7] have defined the Ray-Shooting depth of a point set, and given a topological proof for the existence of points with high Ray-Shooting depth in ℝ2. In this paper, we present an O(n 2 log 2 n)-time algorithm for computing a point of high Ray-Shooting depth. We also present a linear time approximation algorithm.

AB - Over the past several decades, many combinatorial measures have been devised for capturing the statistical data depth of a set of n points in ℝ2. These include Tukey depth [15], Oja depth [12], Simplicial depth [10] and several others. Recently Fox et al. [7] have defined the Ray-Shooting depth of a point set, and given a topological proof for the existence of points with high Ray-Shooting depth in ℝ2. In this paper, we present an O(n 2 log 2 n)-time algorithm for computing a point of high Ray-Shooting depth. We also present a linear time approximation algorithm.

UR - http://www.scopus.com/inward/record.url?scp=80052797167&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052797167&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-23719-5_43

DO - 10.1007/978-3-642-23719-5_43

M3 - Conference contribution

AN - SCOPUS:80052797167

SN - 9783642237188

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 506

EP - 517

BT - Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings

Y2 - 5 September 2011 through 9 September 2011

ER -