Tukey depth & Helly's Theorem

عمق نقطه: مینیمم تعداد نقاطی که می‌توان در یک طرف هر نیم صفحه شامل آن قرار داد. (تعریف در صفحه)

Tukey median: نقطه با بیشترین عمق

قضیه Helly: یک مجموعه از شکل‌های محدب اشتراک دارند، اگر و تنها اگر دو به دو اشتراک داشته باشند.

قضیه: depth(Tukey median) >= n/(d+1)

اثبات:

می‌دانیم می‌شود صفحه‌ای ساخت که دقیقاً k نقطه یک طرف آن باشند اما می‌خواهیم هر نیم‌صفحه‌ای این خاصیت را داشته باشد. Ham Sandwich cut

برای این کار صفحه‌های با nd/(d+1) نقطه را برمی‌داریم چون تعداد نقاطی که درون آنها نیستند حداکثر n/(d+1) است، پس اشتراک هر d+1 تای آنها ناتهی است.

قضیه رادون: هر مجموعه از d+2 نقطه در فضای d بعدی را می‌توان به صورت دو مجموعه مجزا نوشت که پوسته‌ی محدب متقاطع داشته باشند. به نقاط درون اشتراک، نقطه رادون می‌گویند.

یک الگوریتم این است که به صورت متوالی convex hull نقاط را حساب کنیم. با این کار عمق همه‌ی نقطه‌ها به دست می‌آید. بدترین حالت این است که هر بار یک مثلث حساب کنیم که O(n*n log n) = O(n^2 log n) میشه.

الگوریتم با استفاده از دوگان: اگر دوگان نقطه‌ها را بگیریم، یک مجموعه خط به دست می‌آید و نقاط یک طرف خط (نیم صفحه) تبدیل می‌شود به خط های یک طرف یک نقطه. پس عمق تبدیل می‌شود به مینیمم تعداد خط های اطراف نقطه. اگر level ها را حساب کنیم، برای به دست آوردن نقطه با عمق k می‌توانیم هر خطی که بین k-level و (n-i( level را برگردانیم. فقط باید min(n-i,k)=k باشد و طبیعتاً باید n-i > k باشد که نتیجه می‌دهد i<n-k باشد.

می‌شود k-level را در زمان n^2 حساب کرد و زمان‌های بهتر هم دارد.