A V-shape is an infinite polygonal region bounded by two pairs of parallel rays emanating from two vertices (see Figure 1). We describe a randomized algorithm that, given n points and an integer k ≥ 0, finds the minimum-width V-shape enclosing all but k of the points with probability 1 – 1/n^c for any c > 0, with expected running time O(cn²(k + 1)⁴ log n(log n log log n + k))

چکیده

یک شکل V، یک ناحیه چندضلعی نامتناهی است که توسط دو زوج اشعه ساطع شده از دو راس محدود می شود (شکل 1 را ببینید). ما یک الگوریتم تصادفی را توصیف می کنیم که برای n نقطه مشخص و یک عدد صحیح K≥0، شکل V با حداقل عرض را که بر همه ی نقاط به جز k نقطه محیط می شود با احتمال  1-1/n^c برای هر c > 0 و زمان اجرای مد نظر O(cn²(k+1)⁴log n (logn log log n+k)) را پیدا می کند.

1-مقدمه

انگیزش: انگیزه ی این مسئله از دوباره سازی منحنی نشأت گرفته شد: برای مجموعه ی نقاط نمونه برداری شده از یک منحنی در صفحه، شکلی نزدیک به منحنی اصلی به دست می آید. در مقاله [AD13] بیان شده است که در یک ناحیه که منحنی، تغییر جهت تیز دارد، امکان مدلسازی منحنی با استفاده از شکل V به وجود می آید. مولفان بیان می کنند که این طبیعی است که یک مغایرت بررسی شود که می تواند تعداد کمی از نقاط بیرونی را کنترل کند تا نقاط داده ای بد را اصلاح کند. ما آن اختلاف را در اینجا بررسی می کنیم. مسئله، نمونه ای از کلاس بزرگی از مسائل است که به عنوان سوالات بهینه سازی یا جاسازی هندسی شناخته می شود (مقاله [AS98] را برای بررسی ببینید)...