تمرین 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: گراف دوگان این رو می سازه.
