ایده

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

برای مساله یک پارامتر گرفته بود و تابع هزینه رو بر حسب اون به دست آورده بود. بعد با dp روی این پارامتره اومده بود جواب رو به دست آورده بود.

یعنی ایده اش به نظرم به اندازه ی اون باینری سرچ روی مقادیر ارزشمند اومد!

بقیه هم ایده های جالب داشتند:

یکی اومده بود یه مساله ی بدون رنگ رو رنگ آمیزی کرده بود یه طوری که رنگ ها جدا کننده ی مرزهای تصمیم بودند، بعد تابع هدف رو روی اون نسخه ی رنگ آمیزی شده انجام داده بود.

یکی دیگه ایده اش لو رفته بود تقریبا (ساعت قبلش استاد مربوطه درس داد اینو!) این بود که با درخت های بازه ( و سگمنت و امثالهم!) بیایم پوسته محدب بسازیم مثلا. اینم یه جورایی dp است فقط به جای آرایه توی درخته! :))

اون یکی یه کاری روی گراف بود که اومده بود گراف رو به دو قسمت درخت و دور تقسیم کرده بود، برای هر کدوم جواب در آورده بود! البته فکر کنم به نتیجه نرسیده بود! :))

دیگه آخری هم بگم پس: اومده بود زیرمساله ها رو گرفته بود اما مستقل نبودن، بعد تاثیر اون یکی رو توی این اعمال می کرد. کوتاهترین مسیر توی grid بود که توش میومد دایجکسترا(؟!) میزد روی مرز این مربع های کوچکتر کوتاهترین مسیر بین نقاط رو پیدا می کرد. اشکالش هم همین بود که رو هم تاثیر داشتن دیگه، یعنی ممکن بود از توی یه مربع کناری به جواب بهینه ی این مربع فعلی برسی.

میرم مال خودمو درست کنم مثل اینها نشه!

میان ترم هندسه محاسباتی

اصلاحیه: سوال 3 نخواسته بود قطر چند ضلعی محدب رو حساب کنیم که من فکر کردم نوشته، خواسته بود که دو تا نقطه پیدا کنیم که خط واصلش توی این بیفته. باید همون مرتب کردن بر اساس زاویه رو که توی اون نمونه سوالها بود می نوشتم من به جاش اینو نوشتم: (اونم نصفه! :|)

"

اول باید CH اون رو حساب می کردم بعد با rotating calipers (و حساب کردن مینیمم فاصله ی اونها) به دست میاوردیمش:

http://cgm.cs.mcgill.ca/~orm/diam.html

"

واقعا گول خوردم وقتی اون بچه ها گفتن اینها رو نمیده دیگه دوره اش نکردم! :| :(( خیلی بد دادم.

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

سوال1: الف) تعداد یالهای تقاطع n خط n^2 است، تعداد یالهای تقاطع n صفحه چندتاست؟

ب) n نقطه و m خط داریم، تعداد تقاطع ها (نقطه های روی خطها) با عوض کردن تعداد نقطه ها و خط ها ثابت می ماند. (خودم دوگان گرفتم)

ج) ثابت کنید اگه یه سری نقطه رو بر حسب x شون مرتب کنیم و هر نقطه رو با بعدی اش چک کنیم، برای محاسبه ی بیشترین زاویه با محور x کافیه.

سوال 2: ثابت کنید اگه دو تا نقطه روی دایره بیرونی باشه، باید دو تا نقطه هم روی دایره توییه باشه، اگه بخوایم دو دایره ی هم مرکز حساب کنیم که همه ی نقاط بینشون بیفتن. با استفاده از دیاگرام ورونوی و دیاگرام ورونوی دورترین نقطه.

سوال 3: یه چند ضلعی ساده داریم، یه قطر اون رو پیدا کنید. توی O(n).

سوال 4: t تا مثلث داریم، دوگان اینها چی میشه؟ چطوری یه خطی پیدا کنیم که بیشترین تعداد مثلث رو قطع کنه؟

سوال 5: n تا دایره به شعاع یک داریم، در چه صورتی میشه از هر نقطه ی p به هر نقطه ی q رسید؟ (با عبور از اشتراک دایره ها) -- با EMST حل کردم.

سوال 6:  یه افراز از یه مربع می سازیم به این شکل که از پایین ترین نقطه شروع می کنیم یه خط به چپ راست و بالا رسم می کنیم. بعد برای نقطه های بالاتر به ترتیب این کار رو می کنیم. (منظور بر حسب y مرتب شده بودنه). 

الف) ثابت کنید این تعدادش O(n) میشه. (تعداد ناحیه ها)

ب) یه الگوریتم افزایشی برای به دست آوردنش بدید و زمان بدترین حالتش رو حساب کنید.

ج) ثابت کنید اگه رندم نقطه اضافه کنیم، متوسط تعداد به روز رسانی ناحیه ها O(1) میشه.

تمرین 2

2.7 Given a doubly-connected edge list representation of a subdivision where

Twin( e)= Next( e) holds for every half-edge e, how many faces can the

subdivision have at most?

یکی، چون بعدی اش شده اون سر یال یعنی یال دیگه ای توی اون وجه نبوده، یعنی کلا یه خط بوده و همه اش یه فیسه.

2.9 Suppose that a doubly-connected edge list of a connected subdivision is

given. Give pseudocode for an algorithm that lists all faces with vertices

that appear on the outer boundary.

مثلا dfs بزنیم روی dcel ببینیم کجا یال بعدی null میشه.

2.10 Let S be a subdivision of complexity n, and let P be a set of m points. Give

a plane sweep algorithm that computes for every point in P in which face

of S it is contained. Show that your algorithm runs in O((n+m) log(n+

m)) time.

سوییپ معمولی میشه دیگه. علاوه بر دو سر پاره خط ها نقطه های p رو هم میدیم.

2.14 Let S be a set of n disjoint line segments in the plane, and let p be a

point not on any of the line segments of S. We wish to determine all

line segments of S that p can see, that is, all line segments of S that

contain some point q so that the open segment pq doesn’t intersect any

line segment of S.Givean O(nlogn) time algorithm for this problem that

uses a rotating half-line with its endpoint at p.

نمی دونم.

3.6 Give an algorithm that computes in O(nlogn) time a diagonal that splits

a simple polygon with n vertices into two simple polygons each with at

most 2n/3+2 vertices. Hint: Use the dual graph of a triangulation.

هر چند ضلعی رو به دو قسمت تقسیم کنه که هر کدوم حداکثر 2n/3+2 راس دارن؟ خب میشد یه چیزی مثل قطر کشید ولی باید مطمئن باشیم توی اون چند ضلعیه میفته.

جوابها:

خب اولی رو با برهان خلف ثابت کرده.

دومی رو نگفته چک کنید null میشه گفته چک کنید جزو outer boundary میشه یا نه.

سومی همین کارو کرده اما قبلش باید مرتب کنیم. گفته اگه جایی به یه نقطه رسیدیم پاره خط زیری رو ناحیه اش رو پیدا می کنیم و اعلام می کنیم، اگر توی BST چیزی زیر p نبود پاره خط بالایی رو ناحیه اش رو بر می گردونیم. حالت خاص هم داشته دو تا: p روی یه یال باشه، p روی یه راس باشه. توی اولی جوابش دو تا فیس میشه که فیس نیم یال اینوری و اونوری یالی هستند که p روشه، تو حالت دوم همه ی نیم یالهایی که از p شروع میشن فیسشون جوابه. گفته به همون دلیلی که توی سوئیپ ما با برگردوندن نقاط تقاطع زمانمون زیاد نمیشه تو حالت دومی هم هم همین اتفاق میفته.

چهار خیلی جالب بود. گفته که بر اساس زاویه نسبت به p مرتب کنید و توی یه priority queue بریزید و توی نقاط انتهایی پاره خط ها عوضش کنید. اونی که بالاتر از همه است دیده میشه.

سوال 5: گراف دوگان این رو می سازه. 

تمرین 1

این سوالهای اون دانشگاهیه که قبلش امتحانهاش رو حل کردم. این کتاب دومیه خیلی خوب بوده حیف شده زودتر ندیدم بخونمش! :|

1.3 Let E be an unsorted set of n segments that are the edges of a convex

polygon. Describe an O(nlogn) algorithm that computes from E a list

containing all vertices of the polygon, sorted in clockwise order.

یالهای نامرتب CH رو داده، راسها رو به ترتیب ساعتگرد میخواد. خب دو سر پاره خط رو به عنوان نقطه به هر الگوریتم CH ای که بدی برات پیدا می کنه دیگه.

1.8 The O(nlogn) algorithm to compute the convex hull of a set of n points

in the plane that was described in this chapter is based on the paradigm

of incremental construction: add the points one by one, and update the

convex hull after each addition. In this exercise we shall develop an

algorithm based on another paradigm, namely divide-and-conquer.

a. Let P1 and P2 be two disjoint convex polygons with n vertices in total.

Give an O(n) time algorithm that computes the convex hull of P1 ∪P2.

مماس مشترک بالایی و پایینی رو پیدا می کنیم و بینش رو حذف می کنیم. زمان پیدا کردن مماس مشترک که خیلی کمتر از این حرفهاست، زمان حذف کردن هم که یکه. اصلا O(n) چرا با logn حل میشه.

b. Use the algorithm from part a to develop an O(nlogn) time divide-and-

conquer algorithm to compute the convex hull of a set of n points in

the plane.

الگوریتمش هست دیگه، نقطه ها رو نصف می کنی، CH راستی ها، CG چپی ها و ادغام هم O(n).

T(n) = 2T(n/2)+O(n) ==> T(n) = O(nlogn)

1.9 Suppose that we have a subroutine CONVEXHULL available for comput-

ing the convex hull of a set of points in the plane. Its output is a list of con-

vex hull vertices, sorted in clockwise order. Now let S = {x1,x2,...,xn}

be a set of n numbers. Show that S can be sorted in O(n) time plus the

time needed for one call to CONVEXHULL. Since the sorting problem

has an Ω(nlogn) lower bound, this implies that the convex hull problem

has an Ω(nlogn) lower bound as well. Hence, the algorithm presented in

this chapter is asymptotically optimal.

اعضای S رو به نقاط xi, xi^2 تبدیل می کنیم و CH اونها رو حساب می کنیم. بعد مرتب شده بر می گردونه. چون بر اساس زاویه مرتب می کنه که tan a = x^2/x = x

خب ببینیم چقدر از این جواب ها درست بوده!

باید سه تا راس رو در نظر می گرفتیم برای حالت بندی پیدا کردن مماس مشترک. خیلی خوبه که هیچ کس اینو نگفته! :| (سوال 1) کلا 4 تا حالت میشه.

یه سوالو جا انداخته بودم:

2.3 Change the code of Algorithm FINDINTERSECTIONS (and of the pro-

cedures that it calls) such that the working storage is O(n) instead of

O(n+k).

الگوریتمی که گفته یه sweep بوده که قرار بوده تقاطع خطوط رو پیدا کنه. خودش گفته که فقط تقاطع پاره خط های مجاور رو نگه دارید (که خط جارو رو قطع می کنن) گفته n تا پاره خط اند حداکثر که دارن خط جارو رو قطع می کنن پس این میشه O(n). بعد گفته تعداد event ها هم خطیه چون همین ها event هم هستند. (در هر مرحله ی الگوریتم: چون برای مرحله ی بعد حذف می کنیم از n بیشتر نمیشه).

تو سوال یک یادم رفت تکراری ها رو باید حذف کنم! :) خودش بر حسب زاویه مرتب کرده. و گفته از کم به زیاد مرتب کنیم CH میشه.

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

(مال یه دانشگاه دیگه است)

خودش: http://www.cs.iastate.edu/~cs518/exams/final.pdf

جوابش: http://www.cs.iastate.edu/~cs518/exams/final-soln.pdf

خب به سبک همیشه اول من حل می کنم بعد چک می کنم.

قبلش یه چیزی در مورد سوالهای قبلی (میان ترم) بگم اونم اینکه تو سوال گالری با n/3 نگهبان حداکثر میشه کاری کرد که همه ی شکل دیده بشه و با سه رنگ کردن میشه همچین چیزی رو به دست آورد. (میشه مینیمم تعداد راسهایی که یک رنگ هستند.). اثباتش هم این طوری بود که مثلث بندی می کرد می گفت تو هر مثلث یه نگهبان باشه حلله. اثبات اینکه میشه مثلث بندی کرد هم با این گفته که دوگان گراف رو می کشیم، (برای دوگان کشیدن اون وجه بیرونی رو راس نگرفته)، بعد گفته دوگانش یه درخته با حداکثر درجه ی 3، چون اگه یکی رو حذف کنیم ناهمبند میشه. آخرشم با استقرا رنگش کرده.

http://www.cs.wustl.edu/~pless/546/lectures/l6.html

خب حالا برگردیم به حل سوالا. (آخرش نفهمیدم این مثلث بندی دوگانش اون وجه بیرونی رو میخواد یا نه!+چقدر دردناکه آدم جواب تمرینهایی که با بدبختی حل کرده بعدا پیدا کنه تو اینترنت! :|)

1- الف) هر چند ضلعی با y یکنوا رو میشه تو زمان خطی مثلث بندی کرد. درسته، چون همه اش رو میشه به اون راس اولیه وصل کرد مثلث ساخت.

ب) هر گره داخلی به جز ریشه توی kd-tree یک ناحیه مستطیلی موازی یک محور رو مشخص می کنه.

kd-tree یه درخته که هر عمقش یکی از محورهای مختصات در فضای d بعدی رو نصف می کنه. (به درد پیدا کردن نقطه ای می خوره که اول داشتیم بعد گم کردیم! :)) ) یعنی هر عمقی که میگذره یه بار نصف میشه، حالا بعد از بار اولی که نصف شد یه چیزی شبیه مستطیل میشه دیگه. (بیشتر مکعب مستطیل) چون کلا بازه اش محدوده. فکر کنم درسته. (ما که نخوندیم!) -غلطه انگار بازه اش محدود نیست اونی که بازه اش محدوده درخت بازه است.. :))

ج) درسته. یال غیر مجاز یعنی چی؟ :))

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

ه) وقتی الگوریتم خط جاروی fortune رو اجرا می کنیم تا دیاگرام ورونوی رو بسازیم، هر کمانی روی خط ساحلی با یک نقطه ی متفاوت تعریف میشه. غلطه، چون هر نقطه یه سهمی میسازه، که می تونه چند بار توی خط ساحلی بیاد.

و) تعداد یالهای دیاگرام ورونوی با تعداد یالهای مثلث بندی دلانی مساویه. (برای یه مجموعه نقطه) درسته، چون هر یالی بین دو تا فیس ه و هر راس توی یه فیسه، وقتی دوگان می گیریم، هر فیس میشه یه راس و بین دو تا راس یه یاله. (مثال نقض: 4 نقطه روی یک دایره)

ز) حساب کردن تقاطع n تا نیم صفحه، از نظر محاسبه معادل ساختن CH نقاط دوگان خطوط مرزی این صفحه هاست. درسته،

2- یه درخت بازه برای مجموعه ی n تا بازه ... حافظه می گیره و می تونه بازه ی شامل یه نقطه رو در زمان ... بده. فقط دومی رو میدونم که logn میشه. دومی هم logn+k میشه! اولی n میشه.

3- با چه شرایطی arrangement مربوط به n تا خط ماکسیمم تعداد راس، یال و فیس رو داره؟

احتمالا وقتی همه خطها همدیگه رو قطع کنن! (این کافی نیست انگار: باید هیچ سه تایی هم توی یه نقطه قطع نکنند!)

4- نمی دونم منظورش اینه که جایی که می بینه بکشم یا جایی که میتونه ازش رد بشه. (منظورش این بوده که اگه حرکت کنه چه جاهایی رو نمیبینه!)

5- خوشبختانه/بدبختانه نخوندیم!

6- الف) CH نقاط S رو کشیدم بعد از رو مرزش رد شدم. (مرز بالایی نزدیک تر بود!)

ب) خب اگه منظورش مثل قسمت الف باشه که اگه r و s رو مستقیم وصل کردیم و CH مربوط به S رو قطع نکرد که حلله، وگرنه به CH مماس می کنیم و بعد از اون نقطه همین حرکت رو ادامه میدیم. (کلا دو تا مماس میشه این دو تا مسیر رو چک می کنیم.)

7-دوگان: مجموعه خطوط دوگان نقطه های خط l: y=mx+b چی میشه؟

میشه یه دسته خط به مرکز m,-b که اشتراکشون یه نقطه m,-b است. (یعنی اگه کل خط رو بخوایم میشه اشتراک اونها میشه یه نقطه، اگه تک تک نقطه ها رو بخوایم میشه یه سری خط که از یه نقطه میگذرن) -- خودش که ثابت کرده گذاشته توی رابطه اش در آورده، ولی قضیه اینه که این دسته خطی که گفتم یه خط (خط عمودی) رو کم داره!

8- مثلث بندی دلانی (دقت کنید شماره سوالا رو دارم اشتباه می زنم :)) نمی دونم از کجا اشتباه شده ولی دیگه دیره!)

یکی یکی باید نقطه اضافه کنیم و با اون locally Delaney درستش کنیم. از p به سه تا راس مثلثی که توش افتاده (1) وصل می کنیم بعد یال مثلثهای زیری p و 2 و بعد مثلث جدیده با 3 فلیپ میشن. -- ساختمان داده اش انگار این طوریه که تا برگ که بری اون ناحیه رو میده.. درست نفهمیدم و نخوندیم دیگه! :)

9- دیاگرام ورونوی:

الف) ثابت کنید بزرگترین دایره ی خالی که مرکزش توی CH نقاطه روی راس دیاگرام ورونوی میفته. (راهنمایی: برهان خلف)

فرض خلف: p درون یکی از سلول های دیاگرام ورونوی می افتد یا روی یک یال به جز در راس. اگر در یال بیفتد فاصله ی آن از دو نقطه (سابت) متناظر آن یال مساوی است و چون خالی است شعاع دایره از این فاصله کمتر مساوی است. هر چه دایره از محل تقاطع عمودمنصف سایتها با یال دور شود دایره بزرگتر می شود، پس چون در راس قطع نکرده یک دایره ی بزرگتر بوده است. در حالتی که درون یکی از ناحیه ها بیفتد، چون می دانیم در هر سایت فقط یک نقطه است پس  فاصله ی مرکز دایره تا آن نقطه از شعاع کمتر مساوی بوده است، پس فاصله ی مرکز دایره تا نقاط دیگر هم از شعاع دایره بیشتر بوده است، یعنی می توانستیم دایره ی بزرگتری بسازیم.

ب) ثابت کنید اگر روی CH باشد (برخلاف قسمت الف) باید روی یال دیاگرام ورونوی بیفتند.

خودش الف رو گفته فقط دایره رو میشه بزرگتر کرد تا از نقطه های دیگه هم بگذره، برای ب گفته که میشه به سمت راس حرکت داد. (من هر دو رو توی الف گفتم!)

ج) یک الگوریتم بدهید که این بزرگترین دایره را به دست بیاورد. زمان اجرای الگوریتم =؟

خودش گفته یه sweep با الگوریتم fortune بریم و VD بسازیم.

خب بعدش احتمالا باید راسهای این دیاگرام رو تست کنیم تا اونی رو پیدا کنیم که بزرگتره. فقط حالت ب رو چیکار باید کرد؟؟ روی تقاطع CH و ورونوی رو چک کرده..

البته اون قسمتی که از روی ورونوی CH ساخته نفهمیدم (گفته یه ناحیه باز پیدا کنید و ccw حرکت کنید) ولی خب در بدترین حالت میشه جدا حساب کرد.

الآن فهمیدم که CH نقاط سایت رو ساخته، از ورونوی هم برای این استفاده کرده که یه نقطه بیفته توش و جهت رو داشته باشه. بعدش گفته که نصف فاصله ی ضلع CH تا راس ورونوی رو تست کنید برای شعاع دایره.

امتحان هندسه محاسباتی

مال یه دانشگاه دیگه است: http://www.cs.iastate.edu/~cs518/exams/midterm.pdf

1- سه نقطه ی p1 و p2 و p3 داریم، شرط اینکه p3 روی پاره خط p1p2 باشد با ضرب برداری چیست؟

p1p2xp1p3=0

چون وقتی دو بردار هم خط باشند ضرب خارجی شون (سینوس زاویه بین) صفر میشه.

اصلاحیه: این کافی نیست، چون ممکنه نقطه p3 در ادامه ی نیم خط p1p2 بیفته، پس باید یه چک دیگه هم بکنیم که این طوری میشه که از p1 و p2 به p3 دو تا بردار رسم کنیم، اگر همجهت بودن یعنی p3 بیرون پاره خطه، و اگر مخالف جهت هم بودن یعنی روی پاره خط بوده. این هم با ضرب داخلی میشه چک کرد چون کسینوس همجهت ها کسینوس صفره که میشه یک و کسینوس خلاف جهت ها کسینوس 180 درجه است که میشه منفی یک.

2- کدامیک از مجموعه های زیر محدب اند؟

تعریف مجموعه محدب اینه که هر دو نقطه ای اش رو که به هم وصل کنی تو خودش بیفته.

الف) یک نقطه : به انتفای مقدم هست! (چون دو تا نقطه نداره!)

ب) یک مثلث تو خالی: نیست چون دو تا نقطه که رای نیستن به هم وصل کنیم تو این مجموعه (محیط مثلث) نیست.

ج) سهمی: نیست چون اصلا تو نداره که بخواد توش بیفته!

د) بیضی تو پر: هست

3-صحیح/غلط

الف) ؟؟

ب) جواب یک سوال برنامه ریزی خطی اگر یکتا باشه باید روی یک راس ناحیه مجاز باشه = درسته!

ج) تقاطع n تا نیم صفحه (شامل مرزها) نمی تونه یه نقطه بشه! غلطه. مثال نقضش محور مختصات!

4-تعداد مثلثهای یک مثلث بندی چند ضلعی ساده با n راس چیست؟

سه تا راس که برای یه مثلث می خوایم، هر راسی اضافه بشه یه مثلث اضافه میشه. کلا میشه n-3 به علاوه یکی میشه n-2

5- نخوندیم!

6-نخوندیم!

7-نخوندیم!

-----------------

*- doubly connected edge lists

1- فرض کنید e یک نیم یال باشه که یک قسمت مسطح رو مشخص میکنه، کدوم یکی از موارد زیر همیشه درست اند؟

DCEL کلا چهار تا چیز نگه میداره: عنصر بعدی اش، عنصر قبلی اش و راسی که نیم یال بهش وصل شده و نیم یال اون سر یال. هر نیم یال یه فیس (وجه) رو مشخص میکنه. همه رو هم ccw نگه میداره.

الف) اون سر نیم یال e عنصر بعدی اش هیچ وقت e نیست. خب ما میدونیم اون سر نیم یال next(e) قبلی next(e) است و در یک جهت نگه میداره و میتونه هیچی نباشه و بعدش دوباره رو همین برگرده و یه خط بسازه. پس غلطه.

ب) قبلی بعدی e خود  e میشه. درسته!

ج) نیم یال e جزو فیس مجاور e هست. درسته انگار غلطه! :))

د) فیس مجاور e = فیس مجاور بعدی e. درسته دیگه تا وقتی دوباره به e برسه همه دور یه فیس اند.

2- یه قسمت دادن بهتون که 7 تا یال e1,..,e7 داره، و سه تا فیس f1,..,f3. هر یال ei به صورت ei,a و ei,b به دو تا نیم یال تقسیم میشه. جدولها رو با توجه به شکل پر کنید.

face -- outer component -- inner component

f1 -- e3a, e1a, e2a -- e2b, e1b, e3b 

f2 -- e61, e4a, e5a --  e5b, e4b, e6b

f3 -- e7a, e7b -- e7b, e7a

half-edge -- twin -- incident face -- next -- prev

e1a -- e1b -- f2 -- e2a -- e3a

e1b -- e1a -- f1 -- e3b -- e2b

e3a -- e3b -- f2 -- e1a -- e2a

e3b -- e3a -- f1 -- e2b--e1b

e5a -- e5b -- f3-- e6a -- e4a

e5b -- e5a -- f2 -- e4b--e6b

e7a--e7b--f3--e7b--e7b

e7b--e7a--f3--e7a--e7a

3- مساله موزه هنری!

الف) گراف دوگان مثلث بندی بالا رو بکشید.

خلاصه این طوریه که باید به ازای هر دو تا فیس مجاور یه یال بکشید و هر فیس خودش یه راسه.

ب) با سه تا رنگ (اعداد 1 و 2 و3) راسهای گراف رو رنگ کنید. (دو تا از قبل رنگ شده) - این کار رو با دی اف اس انجام بدید.

این دی اف اس ای که میگه باید روی فیس ها بزنید. (راسهای گراف دوگان!)

** در این لحظه ی خاص کشف کردم که حل سوالها روی همون سایت بود! (نمی دونم چرا قبلش ندیده بودم! :دی)

این لینک: http://www.cs.iastate.edu/~cs518/exams/midterm-soln.pdf

4- الف) از رو جواب ببینید دیگه! شبیه آپدیت کردن لینک لیست میمونه فقط باید قبلی رو از روی ccw روی فیس اش تشخیص بدید!

چیزهایی که باید درست کنید: next و prev و origin و twin هستند. (حواستون باشه مثلا prev راس بعدی رو هم تغییر بدید!)

ب) گفته برای تقاطع دو یال چند تا آپدیت باید انجام بشه؟ کلا 4 تا فیس هست، هر کدوم طبق قسمت الف 12 تا آپدیت داره میشه 48 تا.

5-الف) با n تا نقطه ی داده شده یه چند ضلعی (ساده = نه لزوما محدب) بسازید که راسهاش اینها باشند. (با فرض اینکه هیچ سه نقطه ای همخط نیستند)و n>=3

خب تنها چیزی که توی این مهمه اینه که دو تا یال از روی هم رد نشن! (گراف که نیست که چند ضلعیه!). خب برای این دو تا نقطه رو به هم وصل می کنیم و نزدیک ترین نقطه رو به این پاره خط به دست میاریم. بعد از دو سر پاره خط به این وصل می کنیم یه مثلث میشه. این کار رو ادامه میدیم و اینکه نزدیک ترین نقطه است باعث میشه هیچ نقطه ای توی این چند ضلعیه نیفته. فقط باید هر بار که یه نقطه اضافه می کنیم اون نزدیک ترین ضلع بهش رو حذف کنیم!

خودش یه راه بهتری داده که شبیه کادوپیچیه، گفته پایین ترین نقطه (راست ترین در صورت چندتا بودن) رو پیدا کنید، بعد نقطه ها رو بر اساس زاویه شون نسبت به این نقطه مرتب کنید. بعد به ترتیب شروع کنید اینها رو هر کدوم رو به بعدی وصل کنید. اثباتش هم باید مثل اون باشه که می خوایم ببینیم یه نقطه توی یه چند ضلعی هست یا نه بعد میایم زاویه ها رو جمع می زنیم میبینیم اگه 360 شد یعنی بیرونه وگرنه توی چند ضلعیه. پس مهمه که نقطه ای که بر اساسش مرتب می کنیم توی چند ضلعی نیفته!

ب) زمان الگوریتمتون چقدره؟ زمانش میشه زمان مرتب کردن نقاط میشه O(nlogn) چون بعدش فقط یه وصل کردنه که O(n) زمان می بره.

(زمان مال من میشه O(n3) چون باید همه ی ضلع ها رو با همه ی نقاط باقیمونده حساب کنه تا هر راسی رو اضافه کنه!)

ج) چرا این زمان بهینه است؟

( مال من که بهینه نبود! :)) )

خب من ایده ای نداشتم دیدم خودش reduce کرده sort کردن n تا عدد (x) رو به ساختن این چند ضلعی برای نقاط (x,x^2). خب اگه این چند ضلعی رو برای این نقطه ها بسازیم، چرا x ها مرتب میشن؟؟ (کسی ایده ای داره؟ :)) ) خب اگه بیایم زاویه رو حساب کنیم با یه نقطه ی گوشه میشه انتقال مبدا مختصات میشه (x-x0, x^2-x0^2) بعد زاویه اش میشه arctan(x^2-x0^2)/(x-x0) که میشه arctan(x+x0) که خب x0 که ثابته، تانژانت هم که صعودیه، پس اگه این مرتب بشه اون هم مرتب میشه! (پس ایده ای اش همون حساب کردن زاویه بود)

خودش گفته از چپ به راست نقاط چند ضلعی رو چاپ کنید مرتب شده است و چون مرتب کردن امگای nlogn است (کران پایین) پس این هم بهتر از این حل نمیشه.

*** چه عجب تموم شد!