کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414319 680888 2012 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
New constructions of SSPDs and their applications
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
New constructions of SSPDs and their applications
چکیده انگلیسی

We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of n   points in RdRd. In the new construction each point participates in a few pairs, and it extends easily to spaces with low doubling dimension. This is the first optimal construction with these properties.As an application of the new construction, for a fixed t>1t>1, we present a new construction of a t  -spanner with O(n)O(n) edges and maximum degree O(log2n) that has a separator of size O(n1−1/d)O(n1−1/d).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 45, Issues 5–6, July 2012, Pages 200–214
نویسندگان
, ,