فصل 3 vladlen

کاربردهای اپسیلون-نت

*arrangement & point location

-مکان یابی نقطه در arrangement

مکان یابی را به صورت شمارش تعداد ابرصفحه هایی که نقطه کوئری زیر آنهاست، تعریف می کنیم.

ساختمان داده ای که به کار می بریم یک درخت است که در هر راس آن یک زیرمجموعه از ابرصفحه ها است. ریشه کل صفحه هاست. به ازای هر گره از درخت، به صورت بازگشتی زیردرخت آن را می سازیم. فرض کنید کلا n ابرصفحه داشته باشیم. اگر به ازای یک ثابت سراسری n0 بدانیم n<= n0 است این گره یک برگ است و بازگشت تمام می شود. در غیر این صورت ست سیستم (کل صفحات، صفحاتی که اشتراک یک d-simplex در صفحه اقلیدسی d بعدی دلتا با آنها تهی نباشد) می سازیم. این یک زیرسیستم از ست سیستم است که بعد VC آن حداکثر O(d^3 log d) است. پس بعد VC ست سیستم ما حداکثر O(d^3 log d) است که O(1) است چون d را ثابت فرض کردیم. پس قضیه اپسیلون-نت نتیجه می دهد که با نمونه گیری تصادفی در زمان O(n) می توانیم یک 1/r-نت بسازیم برای ست سیستم مان که اندازه اش O(r log r) است. آن را به simplex هایی با استفاده از روش بعد تجزیه می کنیم که به آن "bottom-vertex simplicial decomposition" می گویند.

منظور از تجزیه به simplex ها این است:

1) اجتماع آنها کل فضا را بدهد.

2) اشتراک دو به دوی آنها تهی باشد.

3) هر عضو از مجموعه صفحات منتخب با هر simplex انتخاب شده یا اشتراک تهی داشته باشد یا simplex زیرمجموعه آن باشد.

با استقرا روی تعداد ابعاد به دست می آید:

برای یک بعد خود arrangement جواب است. برای ابعاد بالاتر به ازای هر صفحه از مجموعه F می توانیم X|f و arrangement آن را در آن صفحه حساب کنیم. ...

* جستجوی تقاطع پاره خط ها

با point location و ساختمان داده مناسب می توان در O(n^(d+epsilon)) پیش پردازش (به ازای هر اپسیلون) و زمان کوئری O(log n) به آن جواب داد.

به ازای دو سر پاره خط صفحه ها به دو زیرمجموعه مجزای تقسیم می شوند که از زیر یکی و بالای دیگری می گذرند (و برعکس این!).

*جستجوی بازه ای

مساله simplex range searching : مجموعه P از n نقطه در صفحه اقلیدسی d بعدی داده شده است، می خواهیم P را طوری پیش پردازش کنیم و ساختمان داده ای بسازیم که به ازای simplex S کوئری d بعدی بتوانیم تعداد نقاطی از P را که در آن می افتند بشماریم. (یعنی اشتراک S و P)

با دوگان گرفتن حل می کنیم. یک simplex با d بعد را می توان به صورت تقاطع d+1 نیم ابرصفحه در نظر گرفت. حالا با دوگان گرفتن ابرصفحه به نقطه تبدیل می شود و مساله به مساله ی اول (مکان یابی نقطه) تبدیل می شود.

* جستجوی نزدیک ترین همسایه

مجموعه P از n نقطه در فضای اقلیدسی d بعدی داده شده، آن را طوری به صورت یک ساختمان داده پیش پردازش کنید که به ازای نقطه کوئری داده شده q نزدیک ترین نقطه به آن از بین نقاط P را بدهد.

argmin sqrt( sum_i_1_d(pi-qi)^2 )

(sqrt is monotone) ==> argmin sum_i_1_d (pi-qi)^2 = argmin sum_i_1_d (pi^2)-2sum(pi qi)+sum(qi^2)

(qi^2 is constant for all points: it's query point)

==> argmin (sum(pi^2)-2*sum(pi qi) )

f_p(x) = sum(pi^2) -2sum(pi xi)

این تابع یک ابرصفحه است. کوئری نزدیک ترین همسایه یک x برای تابع بالا می دهد و می خواهد نقطه ای که f_p(x) را مینیمم می کند پیدا کند. این معادل point location در دیاگرام کمینه سازی مجموعه همه ی fp ها است. (دیاگرام ورونوی)

همان کار قسمت اول را انجام می دهیم فقط به جای اینکه تجزیه را برای همه ی ناحیه ها انجام دهیم فقط برای ناحیه های زیر lower envelope انجام می دهیم.

زمان کوئری O(log n) و زمان پیش پردازش O(n^(ceil(d/2)+epsilon)) است.