سوال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.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.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 میشه.
