Date: Dec 6 or 11 (during the last 2 classes)
Present one paper on geometric data structures (20 minutes if you are working alone, or 30 minutes if you are working in a group of 2). The format should be similar to a conference talk. Spend sufficient time on the introduction (problem statement, motivation, general survey of previous and new results). Then describe the key ideas of the new method(s) in the paper. You will not have time to cover all the technical details; pick the part(s) you find most interesting. Point out connection (if any) with techniques we have seen from class. Close with open questions (from the paper, or ones you think of yourself).
Due date: Dec 19 Thursday
Option 1: Write a report (about 10 pages (single-column, single-spaced) if you are working alone, or about 15 pages if you are working in a group of 2), comparing 2 or more papers that address a common problem in geometric data structures. One of the papers may be the paper you have used for your presentation.
Begin with an introduction of the problem and a general survey. Then describe the key ideas of the new methods in your selected papers. Again, you are not supposed to explain all the technical details. Present your own (hopefully easier-to-understand) interpretation, in your own words (do not copy or just paraphrase the descriptions from the papers). Point out similarities and differences between the papers, and their strengths and weaknesses. Point out connections (if any) with techniques from class. Close with open questions, as well as your thoughts on future work and any ideas you may have regarding possible further improvements.
Option 2: do original research! This option is riskier, but even if you do not succeed in solving an open problem, you could still write a general survey of prior work, and explain your failed attempts, partial results on special cases, new variations of the problem, etc. in your report.
Option 3: Implement some existing geometric data structures (from class or from papers) and report on your experimental results.
Some examples are listed below. You are encouraged to find a topic/papers on your own, or ask me for advice. Let me know what you choose by mid-November.