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

من اول معذرت می‌خواهم که موضوع هندسه ترکیبیاتی را در وبلاگ جدا کردم و یک عده پیدا نکرده بودند.

دوم اینکه کیفیت سوالهایی که می‌ذارم روز به روز داره کمتر میشه این سری توی اتوبوس نوشتم و عکس گرفتم. :)

ساختمان داده‌های متحرک

http://www.cs.duke.edu/~pankaj/publications/slides/kinetic-range.pdf

On triple intersections of three families of unit circles

Let p1, p2, p3 be three distinct points in the plane, and, for i = 1, 2, 3, let Ci be a family of n unit circles that pass through pi. We address a conjecture made by Székely, and show that the number of points incident to a circle of each family is O(n11/6), improving an earlier bound for this problem due to Elekes, Simonovits, and Szabó [4]. The problem is a special instance of a more general problem studied by Elekes and Szabó [5] (and by Elekes and Rónyai [3]).

امتحان‌ها

من از زمان تحویل تمرین دکتر آبام نهایت تشکر را دارم! تنها دلیلی بود که من فهمیدم که امتحان‌هام توی خرداده نه تیر! (فقط هندسه توی تیره)

اولین امتحان تقریبی است که ۲۲ است بعدی موازی است که ۲۷ است بعدی ۳ تیر هندسه محاسباتی پیشرفته است.

The Szemerédi-Trotter theorem and the cell decomposition

دریافت
حجم: 475 کیلوبایت

جزوه..

*اگر از گراف G به ازای هر تقاطع انقدر یال حذف کنیم که دیگر تقاطع نباشد به گراف G' می‌رسیم که مسطح است. چون گراف مسطح است تعداد یالهای آن از مرتبه‌ی تعداد رأسهای آن است. پس m' < m+x است که x تعداد تقاطع‌های گراف G است.

*روش احتمالاتی: هر رأس را با احتمال p در گراف نگه می‌داریم. در نتیجه متوسط تعداد رأسها pn، متوسط تعداد یالها p^2 n و متوسط تعداد تقاطع‌ها p^4 n می‌شود. طبق قضیه قبلی تعداد یالها به صورت متوسط جمع تعداد رأسها و تعداد تقاطع‌ها است.

تقاطع پاره‌خط‌ها

منبع: clarkson 89 applications of random sampling in CG

ارائه‌ی هندسه پیشرفته

انقدر مطمئنم که فردا هیچ کس بهم نمره نمیده اصلاً دلم میخواد نروم ارائه بدهم. همه میان ارائه میدن چرت و پرت هیچی ازش نمیشه فهمید بعد من به اونها نمره کامل میدم اونها به من صفر. این همه کارشناسی که درس رو ندارن میان سر کلاس نمره میدن به ارشدها قطعاً به حساب دوست-رفیق بازیه. آخه کجای دنیا این طوری نمره میدن؟ اصلاً همین که هیچ کس تهش هیچی نمی‌پرسه خودش به قدر کافی گویاست. من هم این ترم نپرسیدم هیچی گفتم کمتر از نمره‌ام کم کنن! :| باز از اعداد تصادفی که هر ترم تولید میشه برای ترتیب ارائه‌ها که بهتره! :| حالا یکی نیست بگه مقاله‌ای که من قراره ارائه بدم که خود شما انتخاب کردید استاد محترم، دیگه چرا وقت ارائه‌ی من رو ۵ دقیقه می‌کنید که نرسم توضیح بدهم؟ اونوقت یکی مثل عزیزکرده کلاس میاد عین مطالب سر کلاس رو تکرار می‌کنه که کاملاً توهین به شعور آدمه و میره. آخرشم من باید از استعدادهای اونها استفاده کنم!!! واقعاً اینجا دانشگاه به درد نخوریه. (از هر جهت)

موضوع ارائه: net & prune روشی برای حل مسائل فاصله اقلیدسی در زمان خطی (expected)

دریافت
حجم: 994 کیلوبایت

تمرین سوم هندسه محاسباتی پیشرفته

http://ce.sharif.edu/courses/92-93/2/ce795-1/assignments/files/assignDir2/A3.pdf

A Webpage on The Erdos Distance Problem by William Gasarch

https://www.cs.umd.edu/~gasarch/erdos_dist/erdos_dist.html