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.

- range searching for fat rectangles: C., Nekrich, and Smid (WADS'19)
- "range sampling": e.g., Afshani and Wei (ESA'17), Afshani and Phillips (SoCG'19) (TAKEN)
- range searching lower bounds: e.g., a recent paper is Afshani (SoCG'19) (TAKEN)
- 3D orthogonal point location: e.g., C., Nekrich, Rahul, and Tsakalidis (ICALP'18), de Berg, van Kreveld, and Snoeyink'95 (TAKEN)
- 3D nonorthogonal point location: e.g., Preparata and Tamassia (1992), Goodrich and Tamassia (1998) (TAKEN)
- 2D dynamic point location for disconnected subdivisions: Oh and Ahn (SoCG'18)
- point location in high dimensions: e.g., Meiser'93, Meyer auf der Heide'84, Ezra and Sharir (SoCG'17), Kane, Lovett, and Moran (STOC'18) (the last one interestingly uses a technique from machine learning) (TAKEN)
- dynamic geometric data structures via shallow cuttings: my SoCG'19 paper
- approximate polytope membership queries (which are related to approximate nearest neighbors): Arya, da Fonseca, and Mount (STOC'11), or one of their later papers (TAKEN)
- space-efficient approximate range searching: Wei and Yi (SODA'13)
- locality sensitive hashing without errors: Pagh (SODA'17), Ahle (FOCS'17), Wei (SODA'19) (TAKEN)

- Search for papers with Google Scholar
- Browse through recent conferences SoCG, SODA, FOCS, STOC, ICALP, ESA, WADS, SWAT, CCCG, ISAAC, COCOON, etc., with DBLP
- Check out latest papers on the arxiv
- Note: many papers have both a conference and a journal version; use the more up-to-date journal version if available