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 -