Fast construction of nets in low-dimensional metrics and their applications

Sariel Har-Peled, Manor Mendel

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near linear and the space being used is linear.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)1148-1184
عدد الصفحات37
دوريةSIAM Journal on Computing
مستوى الصوت35
رقم الإصدار5
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2006


أدرس بدقة موضوعات البحث “Fast construction of nets in low-dimensional metrics and their applications'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا