epsilon sample & epsilon net

epsilon sample: اگر O(1/eps^2 lg 1/eps) نقطه را به صورت تصادفی یکنواخت برداریم با احتمال زیادی در هر نیم فضا نسبت نقاط حفظ می‌شود.

epsilon net: می‌توان مجموعه‌ای از O(1/epsilon lg 1/epsilon) نقطه برداشت که در هر نیم‌فضا حداقل epsilon*n نقطه باشد.

epsilon net: اگر یک فضای بازه با بعد VC برابر d داشته باشیم، یک epsilon net با اندازه‌ی O(d/eps lg d/eps) دارند و یک epsilon sample با اندازه‌ی O(d/eps^2 lg d/eps) دارند. برای به دست آوردن مجموعه‌های متناظر به همین تعداد نقطه را تصادفی یکنواخت انتخاب می‌کنیم.

مثال: جستجوی بازه‌ای

اگر بازه‌ی مورد جستجو مستطیل‌های با اضلاع موازی محورهای مختصات باشند، با epsilon sample به خطای جمعی epsilon*n می‌رسیم.

مثال: تقریب نقطه مرکزی

نقطه‌ای را از مجموعه نقاط برگردانید که هر نیم‌فضای گذرنده از آن نقطه شامل حداقل 

(1/(d+1) - epsilon) n

نقطه باشد.

یک epsilon sample می‌گیریم و نقطه‌ی مرکزی آن را حساب می‌کنیم و به عنوان تقریب نقطه مرکزی مجموعه نقاط اصلی برمی‌گردانیم.

| (r/(d+1)) / r - |P intersection h| / n | <= epsilon

++