k-level

نسخه‌ی متحرک: یک سری نقطه‌ی متحرک روی یک خط داریم که سرعت آنها ثابت است (در نتیجه معادله‌ی زمان مکان آنها خطی است) می‌خواهیم ببینیم نفر k-ام چند بار عوض می‌شود.

x=vt+x0

متناظر با در نظر گرفتن نمودارهای آنها و بررسی جا به جا شدن‌ها است. (k-level) یعنی قسمتی از نمودار که k خط زیر آن هستند. پس تعداد نقاط k-level تعداد تغییرهای نفر k-ام است.

حالت‌های خاص:

یک مجموعه خط داریم، lower envelope آنها چند یال دارد؟ 1-level را می‌توان در زمان O(n) حساب کرد. (با linear programming)

به طور مشابه برای n-level یا upper envelope.

دوگان مسأله:

دوگان خط‌ها را می‌گیریم یک مجموعه نقطه به دست می‌آید. هر نقطه جواب هم تبدیل به یک خط می‌شود که باید k نقطه یک طرف آن باشند. تعداد تغییرهای نفر k-ام برابر است با تعداد خط‌هایی که این خاصیت را دارند، به شرطی که دقیقاً خط گذرنده از دو نقطه را در نظر بگیریم.

جواب:

بین هر دو رأس k-level که زاویه محدب دارند، حداکثر می‌توانند همه‌ی خطوط زیر آن بیایند که یک زنجیره محدب با O(k) ضلع می‌سازد.

هر نقطه را به صورت یک رأس و هر خطی که k نقطه را از بقیه جدا می‌کند یک یال در نظر می‌گیریم. (طبق تعریف دقیقاً از دو نقطه می‌گذرد.)

نتیجه: هر خط عمودی O(k) یال گراف را قطع می‌کند.

هدف ما پیدا کردن همه‌ی یالهای گراف است. n/m خط عمودی رسم می‌کنیم که بین هر کدام m نقطه باشد. هر خط حداکثر O(k) یال را قطع می‌کند. درون هر ناحیه حداکثر m^2 یال داریم (گراف کامل). پس در کل داریم:

|E| = O(n/m * m^2 + n/m*k)

m = sqrt(k) ==> |E| = O(n sqrt(k))

که m بالا حالتی که دو جمله مساوی می‌شوند و |E| ماکسیمم می‌شود.

بهبود:

تعداد کل تقاطع‌های یالهای گراف O(n^2) است. تعداد نقاط n است پس تعداد خط‌های گذرنده از آنها n^2 است پس تعداد تقاطع‌های ممکن n^4 است که اتفاق نمی‌افتد.

*** اینجا به قسمتی می‌رسیم که کلاً در کلاس بحث نشد و آن این است که چطور زنجیره‌های محدب ساخته می‌شوند؟

از منفی بینهایت شروع می‌کنیم و خط با i-امین بزرگترین شیب را طی می‌کنیم. تنها تقاطع k-level با k-chain در رأسهای محدب است، چون دو یال مجاور یک رأس مشترک بین k-level و k-chain حتماً در k-level نیستند.

ویژگی‌های زنجیره‌های محدب:

۱- همه‌ی رأسهای k-level با یک رأس محدب پوشانده می‌شوند و برعکس. (رأس جدید نداریم)

۲- زنجیره‌های محدب رأسهای مجزا و غیرتکراری دارند.

۳- همه‌ی arrangement (چیدمان) خطوط زیر k-level را می‌پوشانند. در نتیجه همه‌ی رأسهای چیدمان که زیر k-level هستند نقاط تقاطع دو زنجیره محدب هستند.

۴- همه‌ی خطوطی که در ساخت زنجیره‌ی i-ام نقش دارند lower envelopeشان همان رأسهای زنجیره را دارد.

***

حالا از اینجا نتیجه می‌شود که اگر دو یال تقاطع داشته باشند، نقطه‌ی تقاطع آنها در دوگان خطی است که مماس بر زنجیره‌های گذرنده از آن نقطه‌ها است که نتیجه می‌دهد که هر دوی آنها در یک زنجیره محدب هستند اما این در فضای اولیه به معنی داشتن رأس مشترک است (تقاطع در رأس) که می‌دانستیم وجود ندارد. (تناقض)

پس حداکثر تعداد تقاطع‌های هر دو یال به اندازه‌ی تعداد مماس‌های مشترک این زنجیره‌ها است که اگر بین همه‌ی حالت‌ها جمع کنیم همان تعداد رأسهای چیدمان خطوط است که O(n^2) است. (به صورت دقیق‌تر O(nk) است)

اثبات: حالا با استفاده از لم تقاطع داریم:

O(n+n^2/3 x^1/3) = O(n+n^2/3*(nk)^1/3) = O(nk^1/3) = O(n^4/3)

چون تعداد رأسهای گراف n تا است که تعداد نقاط است و تعداد تقاطع‌های آن هم O(nk) است که از روی دوگان آن که چیدمان خطوط بود به دست آوردیم.

-----------------------------------------------------------------

مسائل مرتبط:

*تعداد یالهای level های کمتر مساوی k چندتا است؟ (در جزوه اشتباهی گفته شده رأسها)

با جمع کردن آنها بر خلاف چیزی که توی جزوه هست حتی به همان کران بد هم نمی‌رسیم.

جواب واقعی O(nk) است که (برای چیدمان) می‌گوید هر رأس حداکثر j^2 تا تقاطع دارد (j تعداد levelها) که کلاً O(nk) رأس دارد (چون هر level حداکثر n تا خط دارد و کلاً k تا level داریم) پس در کل O(nkj^2) است که O(n k^1/3 j^2/3) را می‌دهد. (برای اثبات آن از یک قضیه دیگر خارج از مقاله کمک گرفته بود.)

پس جواب درست این سوال که برای k=j خواسته است O(nk) است.

--------------------------------------------------------------

روش کلارکسون:

از probabilistic method استفاده می‌کنیم که اثبات قضیه با استفاده از احتمال است و اندازه‌ی k-level را حساب می‌کنیم. در زیرگراف تصادفی به دست آمده اندازه‌ی k-level برابر O(nk) به دست می‌آید که با جایگذاری در crossing lemma (لم تقاطع) به O(nk^1/3) می‌رسیم.

(کلاً چیزی از مقاله‌اش سر در نیاوردم)