فاصله‌ی نقاط متحرک

سوال تمرین هندسه پیشرفته بود که ساختمان داده‌ای بسازید که اعلام کند که مجموعه نقاط متحرک فاصله‌‌ی نرم بینهایتشان در این لحظه از ۱ کمتر هست یا نه و این شرط را هم داشت که نقاط به صورت افقی یا عمودی حرکت می‌کنند. حالا چیزی که من می‌خواهم حل کنم حالتی است که هر حرکت دلخواهی داشته باشند.

سوال Convex Hull نقاط متحرک را به خاطر بیاورید. حالا دور هر نقطه یک ناحیه با فاصله‌ی ۱ (نرم بینهایت) از آن رسم کنید. هدف ما تشخیص تقاطع داشتن این ناحیه‌ها با هم است. چون این ناحیه نقاطش نسبت به نقاط ورودی ثابت هستند، می‌توانیم معادله‌ی آنها را بر حسب معادله‌ی این نقطه به دست بیاوریم و به چند تا نمودار متقاطع برسیم. حالا با همان روش قبلی (tournament tree) و جاروب روی محور زمان می‌توانیم جواب مسأله را به دست بیاوریم.