محاسبه کوچکترین توپ محیطی

*روش افزایشی

هر بار یک نقطه را اضافه می‌کنیم و توپ محیطی را حساب می‌کنیم تا شامل همه نقاط شود. این کار را با استفاده از این نکته که هر نقطه جدید حتما روی محیط می‌افتد انجام می‌دهیم.

حالا باید ضریب تقریب آن را به دست بیاوریم. دایره جواب بهینه را در نظر می‌گیریم. فاصله‌ی مرکز دایره i-ام تا نقطه i-ام برابر شعاع دایره i-ام است و اگر آن را امتداد دهیم قسمت دیگر حداکثر سه برابر این قسمت است. می‌دانیم طول وتر از قطر کمتر است پس از اینجا ضریب تقریب ۳/۲ به دست می‌آید.

؟؟ چرا سه نقطه‌ی pi,ci,c(i-1) هم‌خط اند؟

*روش تکراری

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

جواب تمرین اول هندسه پیشرفته (مسائل حل نشده)

sublinear algorithms mit

عمرمون بر فناست اگه اینها رو ندونیم! :)

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec13/lec13.pdf

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec16/lec16.pdf

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec18/lec18.pdf

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec15/lec15.pdf

مرجع:

http://stellar.mit.edu/S/course/6/fa07/6.895/materials.html

دلیل اینکه در هندسه محاسباتی پیشرفته است روش‌های merge and reduce و مثل آن است که در این درس آمده است.

Social and Information Network Analysis

http://www.stanford.edu/class/cs224w/index.html

هندسه پیشرفته MIT

(اولش هندسه محاسباتی مقدماتی هم دارد. شما از بقیه اش بخونید!)

http://people.csail.mit.edu/indyk/6.838/

الگوریتم تقریبی MIT

http://courses.csail.mit.edu/6.891-s00/

پایان نامه کارشناسی در مورد الگوریتم تقریبی

http://www.seas.upenn.edu/~sassadi/stuff/papers/thesis.pdf

صندلی‌های نوی آزمایشگاه

صندلی‌های نو آوردن برامون! :) (۱۰ تا!)

الآن من حاضرم برای بهبود وضع آزمایشگاه میزها رو خودم دستمال بکشم! :)

جدا از اینکه دور صندلی‌ها از این محافظٰ‌های حباب‌دار هست (وسیله سرگرمی!) همین که به فکر ما هستند کلی ارزشمنده. من اعتراف می‌کنم در این چند دقیقه روحیه و امید من زیر و رو شده!

اصلاحیه تمرین الگوریتم تقریبی

سوال ۲ برای اینکه تقریب ۱-اپسیلون به دست بیاورید به جای اینکه در نامساوی c.OPT بگذارید ۱-اپسیلون بگذارید. در این صورت جواب بر حسب اپسیلون به دست خواهد آمد. همان طور که از صورت سوال هم مشخص است اپسیلون باید از c بیشتر باشد.

Terrain Visibility with Multiple Viewpoint

http://arxiv.org/pdf/1309.4323v1.pdf