کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
415416 | 681207 | 2013 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating majority depth
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the problem of approximating the majority depth (Liu and Singh, 1993) of a point q with respect to an n-point set, S, by random sampling. At the heart of this problem is a data structures question: How can we preprocess a set of n lines so that we can quickly test whether a randomly selected vertex in the arrangement of these lines is above or below the median level. We describe a Monte Carlo data structure for this problem that can be constructed in O(nlogn) time, can answer queries in O((logn)4/3) expected time, and answers correctly with high probability.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 9, November 2013, Pages 1059–1064
Journal: Computational Geometry - Volume 46, Issue 9, November 2013, Pages 1059–1064
نویسندگان
Dan Chen, Pat Morin,