Instructions

Complete all assigned problems below for your section (437 or 537). Each problem is equal weighted at 20% of the point value for the assignment (equivalently, 2/10 points for 437, 1.6/8 points for 537). You may choose to complete any unassigned problems from the other section for extra credit weighted at 5% (equivalently, 0.5/10 for 437, 0.4/8 for 537).

Whenever you are asked to present an “algorithm,” you should present three things: the algorithm, an informal proof of its correctness, and a derivation of its running time. Remember that your description is intended to be read by a human, not a compiler, so conciseness and clarity are preferred over technical details.

Giving careful and rigorous proofs can be quite cumbersome in geometry, and so you are encouraged to use intuition and give illustrations whenever appropriate. Drawing pictures can be enormously helpful to understanding a problem and explaining the solution. Beware though that a poorly drawn figure can make certain erroneous hypotheses appear to be “obviously correct.” Unlike in-class assignments, you should strive to be thorough and convincing when describing intuition.

Also, unless otherwise stated, you may assume that any geometric primitive involving a constant number of objects each of constant complexity can be computed in \(O(1)\) time.

Solutions must be submitted via Gradescope. While I prefer typeset solutions, e.g. in LaTeX, handwritten is OK provided they are clear to read. You may find this tutorial from Overleaf helpful. We reserve the right to refuse regrading any assignment that we cannot read clearly. By contrast, typeset solutions reserve the right to always be regraded within the parameters set out in the syllabus.


Rules and Regulations

All work is meant to be completed individually. Explicitly, this means that:

  • You should not work in a group.
  • You should not seek out the solutions to these problems from your classmates.
  • You should not share the solutions to these problems with your classmates.

Doing any of these is considering cheating and will be dealt with using the standard procedure for academic dishonesty.

You are allowed to discuss general solution strategies with your classmates. Since exam problems may be modifications of homework problems, it is not a good idea to pass too much information to your classmates, since this will deprive them from the exploration process of winnowing down the multitude of possible solution strategies to the final one.

Regardless, when it comes to writing your solution, you must work independently.

Besides yourself, you may use any results from class or from any standard textbook on algorithms and data structures. Also, you may use results from geometry that: (1) have been mentioned in class, (2) would be known to someone who knows basic geometry or linear algebra, or (3) are intuitively obvious. If you are unsure if a source is OK to use, please feel free to check with me first.

If you use any books, papers, web pages, or other inanimate information sources, you must cite them in your completed solution. In particular, this includes any resources you may have discovered through an internet search. While the external references listed above are free to use, it is not OK to use any other person’s homework solutions or sample solutions that you may have found on the web or otherwise. Some of the homework questions this semester have been used before by me or other teachers at other institutions, and you’re on your honor to not consult the solutions.

Please inquire with the instructor if you need clarification on anything in the readings, the lectures, this homework assignment, or the rules.


437 Problem Set

  1. BCKO, Exercise 1.1a (only complete part a: intersection of convex sets is convex)

  2. BCKO, Exercise 1.3 (sorting edges of a convex polygon)

  3. BCKO, Exercise 1.8 (divide and conquer convex hulls)

  4. BCKO, Exercise 2.8 (DCEL traversal of adjacent vertices and bounding faces)

  5. BCKO, Exercise 2.10 (plane sweep computing containing faces in a subdivision for a point set)


537 Problem Set

  1. BCKO, Exercise 1.6b (convex hull of non-convex polygon in \(O(n)\))

  2. BCKO, Exercise 1.8 (divide and conquer convex hulls)

  3. Let \(P\) be a set of \(n\) points in the plane. A point \(p \in P\) is maximal if there does not exist any other point in \(P\) that is both above and to the right of \(p\).

    1. Give a four-point example \(P\) that has both a maximal point not on the convex hull, and a convex hull point that is not maximal.

    2. The set of maximal points and convex hulls in the plane are similar in many respects. A point \(p\) lies on the convex hull of a set \(P\) if and only if there is a line passing through \(p\) such that all the points of \(P\) lie on one side of this line. Provide an analogous assertion for a maximal point in terms of a different shape.

    3. Devise an analogue of Graham's convex hull algorithm for computing the set of maximal points in \(O(n\log n)\) time. Briefly justify your algorithm's correctness and derive its running time. (You do not need to explain the algorithm "from scratch", that is, you can explain what modifications would be made to Graham's scan.)

  4. BCKO, Exercise 2.11 (intersection of circles)
    Some notes:

    • Your algorithm must be correct even though one circle may be nested within another without intersecting

    • Explain clearly (1) what the sweep-line status stores and what data structure is used to store this information and (2) what future events are stored and what data structure is used.

    • You may assume that you have access to whatever primitive operations that you need in constant time. For example, if you want to determine (a) whether two circles intersect, (b) the coordinates of an intersection, (c) the intersection of a line with a circle, (d) whether a point is contained within a circle’s interior, etc., you may simply assume the existence of a function that runs in \(O(1)\) time.

  5. BCKO, Exercise 2.14 (line segments visible to a point)