چکیده
یک شکل V، یک ناحیه چندضلعی نامتناهی است که توسط دو زوج اشعه ساطع شده از دو راس محدود می شود (شکل 1 را ببینید). ما یک الگوریتم تصادفی را توصیف می کنیم که برای n نقطه مشخص و یک عدد صحیح K≥0، شکل V با حداقل عرض را که بر همه ی نقاط به جز k نقطه محیط می شود با احتمال 1-1/nc برای هر c > 0 و زمان اجرای مد نظر O(cn2(k+1)4log n (logn log log n+k)) را پیدا می کند.
1-مقدمه
انگیزش: انگیزه ی این مسئله از دوباره سازی منحنی نشأت گرفته شد: برای مجموعه ی نقاط نمونه برداری شده از یک منحنی در صفحه، شکلی نزدیک به منحنی اصلی به دست می آید. در مقاله [AD13] بیان شده است که در یک ناحیه که منحنی، تغییر جهت تیز دارد، امکان مدلسازی منحنی با استفاده از شکل V به وجود می آید. مولفان بیان می کنند که این طبیعی است که یک مغایرت بررسی شود که می تواند تعداد کمی از نقاط بیرونی را کنترل کند تا نقاط داده ای بد را اصلاح کند. ما آن اختلاف را در اینجا بررسی می کنیم. مسئله، نمونه ای از کلاس بزرگی از مسائل است که به عنوان سوالات بهینه سازی یا جاسازی هندسی شناخته می شود (مقاله [AS98] را برای بررسی ببینید)...