Weekly Note 3, DM45, spring 2007

Lecture February 21

• Polygon Triangulation (chapter 3).

Discussion Section February 19

• Exercises 2.1, 2.2, 2.3, 2.4, 2.14.
• Assume that we have n disjoint horizontal line segments and m disjoint vertical line segments. Give an O((m+n)log(m+n)) algorithm for finding the number of intersection points among the horizontal and vertical lines. Note that intersections point should not be reported; merely counted.
• Finish-up topics from last lecture, if time permits.