The following is a tentative list of main topics. (Students who have taken CS763 may have seen some of the problems before, but we will discuss them in greater depth, approaching current research level.)
See guidelines for presentation and project.
For finding papers on the web, try Google Scholar, DBLP, and CiteSeerX. The key conferences in the area are SoCG and SODA; other relevant conferences include FOCS, STOC, CCCG, WADS, ESA, ...
May 2: Introduction. Orthogonal range searching. k-d trees.
May 6: Priority search trees and Cartesian trees (for 2D 3-sided). Range trees (e.g., 2D range reporting in O(n log n) space, O(log n + k) time).
May 9: Improving space by bit packing tricks (2D range counting in O(n) space, O(log n) time by Chazelle'88). Improving time by word RAM techniques... Detour in 1D predecessor search: van Emde Boas trees.
May 13: Detour in 1D predecessor search (cont'd): fusion trees. 2D and 3D dominance emptiness by using "staircases". dD general range emptiness in O(n polylog n) space, O((log n/loglog n)^{d-3}loglog n) time.
May 16: Improving both space and time...
Alstrup, Brodal, and Rauhe's grid-based method (2D emptiness in O(n loglog U)
space, O((loglog U)^2) time). C., Larsen, and Patrascu's method based on succinct
DS techniques (2D emptiness in O(n loglog U) space, O(loglog U) time).
May 20: Point location. The naive slab method.
The segment tree method.
May 27: A method based on persistent data structures. A method based
on planar separators.
May 30: A method based on random sampling (Clarkson-Shor style).
June 3: Orthogonal planar point location on the word RAM.
June 6, 10: Nonorthogonal planar point location on the word RAM.
June 17: Nonorthogonal range searching. Willard's partition tree
(O(n) space, O(n^{0.793}) time in 2D, via the ham-sandwich cut theorem).
Point/line duality. A cutting tree (O(n^{4.82}) space, O(log n) time in 2D).
June 20: Clarkson's cutting tree (O(n^{d+eps}) space, O(log n) time).
Cutting lemma (proof by sampling).
June 24:
Matousek's partition tree (O(n) space, O(n^{1-1/d+eps}) time).
Partition theorem (proof by iterative reweighting).
Time/space trade-offs. Applications to combinatorial geometry (e.g., Szemeredi-Trotter theorem, Erdos' unit distance
problem).
June 27:
3D halfspace range emptiness by using lower envelopes.
3D halfspace range reporting by shallow cuttings.
Dynamic data structures.
July 4:
Dynamic convex hulls: Overmars and van Leeuwen's hull tree.
General dynamization techniques: the "logarithmic method".
July 8, 11:
General dynamization techniques (cont'd): the "square root method" and
an offline dynamic method. Klee's measure problem: dynamic 2D
in O(sqrt{n}log n) time (and thus static 3D in O(n^{3/2}log n) time).
July 15, 22:
Approximate nearest neighbor search.
A grid method (for fixed radius). A (compressed) quadtree method.
A method based on Z-ordering and (randomized or deterministic) shifting.
The high dimensional case: locality sensitive hashing.
Student presentations