CS 598 TC, Spring 2017

Presentation and Project Guidelines

Presentation:

The presentations will be in the last 3 classes (Apr 26, Apr 28, and May 3). Contact me (e.g., after class, during my office hours, or by e-mail) to pick a time slot and to specify your paper selection.

Tips: The format should be similar to a conference talk. Spend sufficient time (about half the talk) on the introduction -- problem statement, motivation, comparison of previous vs. new results. Then describe the key ideas of the new method(s). You will not have time to cover all the technical details; pick the part(s) you find most interesting/entertaining. Point out connection (if any) with techniques we have seen from class. Close with open questions (mentioned in the paper or that you think of yourself).

Project:

A report of about 10-15 pages (single-column, single-spaced), on a comparison of 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.

Due date: before May 12, Friday, 5pm.

Tips: 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 just copy or paraphrase the descriptions from the papers). Point out similarities and differences between the papers, and their strengths and weaknesses. Again, 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.

Alternative: 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.

Suggestions/Examples:

Below are just some random examples. Feel free to find a topic/papers on your own, or ask me for advice.

• Meiser ('93): point location in high nonconstant dimensions (see also Ezra and Sharir (SoCG'17) for some related recent developments)
• Agarwal and van Kreveld ('96) solved several problems related to Assignment 1, Question 3; could you get better, sublogarithmic time for the orthogonal case, using newer range searching techniques?
• Kaplan, Sharir, and Verbin (SoCG'06): offline colored range searching, surprisingly using matrix multiplication...
• More complicated variants of range searching such as "range closest pair" (Sharathkumar and Gupta (CCCG'06) -- could some of the logs be improved?) -- TAKEN; or "range MST" (Arya, Mount, and Park (SoCG'15))
• Lower bounds on orthogonal range searching, e.g., Grolund and Larsen (ICALP'16), or a brand new(!) paper by Larsen, Weinstein, and Yu...
• Preparata and Tamassia (SIAM J. Comput.'92): point location in 3D
• Agarwal, Matousek, and Sharir (FOCS'12) (see also Matousek and Patakova): nonorthogonal nonlinear range searching, using a new algebraic geometry approach
• BSP trees, e.g., Hershberger, Suri, and Toth (SoCG'04)...
• Geometric data structures for probabilistic data, e.g., Agarwal, Aronov, Har-Peled, Philips, Yi, and Zhang (ESA'14) (TAKEN)
• Giyora and Kaplan (SODA'07) and Blelloch (SODA'08): dynamic orthogonal point location (TAKEN)
• Nekrich (ISAAC'11): dynamic stabbing-max
• Afshani and C. (ESA'08): dynamic connectivity for orthogonal line segments
• Pagh (SODA'16): LSH without false negatives, for approximate nearest neighbor search in high-dimensional Hamming space (see also a new paper by Ahle)
• Andoni, Razenshteyn, and Nosatski (SODA'17): an alternative to LSH
• Arge, Brodal, and Rao (SoCG'08): external-memory (dynamic) planar point location
• Nekrich (ISAAC'10): external-memory dynamic orthogonal range searching
• Arge, Brodal, Fagerberg, and Lausten (SoCG'05): cache-oblivious orthogonal range searching
• Brodal et al. (ESA'12): succinct DS for range minima for 2D arrays
• Frahling, Indyk, and Sohler (SoCG'05): dynamic streaming algorithms for Euclidean min spanning trees, etc.
• 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, or the new SoCG'17 accepted papers
• Note: many papers may have both a conference and a journal version; use the more up-to-date, journal version if exists