## Geometric Data Structures

### Instructor

Timothy Chan (Siebel 3230, tmc "at" illinois.edu, office hours: Wed 2:30-3:30 or by appointment)

### Meeting Time and Place

Wed & Fri 11:00-11:15, Siebel 1103

### Course Overview

This course is about data structures in computational geometry. We will discuss fundamental techniques and recent theoretical developments for a variety of basic geometric data structuring problems in a variety of models. Possible topics include:

• Orthogonal range searching: from basic methods (such as range trees) to current best results (such as my paper with Larsen and Patrascu)
• Point location: from standard solutions (segment trees, fractional cascading, persistence, planar separators, ...), to more recent sublogarithmic methods on the word RAM
• Nonorthogonal range searching: partition trees, cutting trees, random sampling, iterative reweighting, shallow cuttings
• Dynamic data structures: dynamic convex hull, dynamic point location, general dynamization techniques
• Approximate nearest neighbor searching: quadtrees, shifting, z-ordering, locality sensitive hashing
• Big data: external-memory geometric data structures, geometric streaming algorithms, ...

Prerequisite: a solid background in algorithm design and analysis (e.g., at the level of CS 374) is assumed.

### Course Work

• 4 assignments (problem sets), worth 40%
• presentation, worth 20%
• a project (reading some papers and writing a report, or implementing some data structures, or doing some original research), worth 40%

(Assignments and projects may be done individually or in groups of 2.)

### References

There is no required textbook, but you may find the following general references useful:

### Lectures

(I'll provide copies of my handwritten notes, and links to relevant papers, below...)

Aug 28, 30, Sep 4: Introduction. Orthogonal range searching.

• k-d trees (O(n) space, O(n^{1-1/d} + k) time; see Sec 5.2 of BCKO)
• Priority search trees and Cartesian trees for 2D 3-sided emptiness/reporting (O(n) space, O(log n + k) time; see Sec 10.2 of BCKO and wikipedia page)
• Range trees (O(n log^{d-1} n) space, O(log^{d-1} n) time; see Sec 5.3-5.6 of BCKO)
• my notes

Sep 6, 11:

• Improving space by bit packing: Chazelle'88 for 2D counting (O(n) space, O(log n) time; see Sec 3.1 of paper)
• Improving time: warm-up with 1D predecessor search
• van Emde Boas trees (O(n) space, O(loglog U) time; see wikipedia, or the Cormen et al. textbook, 3rd ed.)
• fusion trees (O(n) space, O(log_w n) time, but rough sketch only; see Fredman and Willard's paper)
• my notes

Sep 11, 13, 18:

• Improving time in 2D (O(n log n) space, O(loglog U) time (for emptiness))
• Improving time and space in 2D: Alstrup, Brodal, and Rauhe's grid-based method (O(n loglog U) space, O((loglog U)^2) time; see Sec 3 of paper)
• Improving time and space in 2D: C.-Larsen-Patrascu'11 (O(n loglog n) space, O(loglog U) time; see Sec 2 of paper)
• my notes

Sep 18, 20: Planar point location.

• The naive slab method (O(n^2) space, O(log n) time)
• The segment tree method (O(n log n) space, O(log^2 n) time; see Sec 10.3 of BCKO)
• ... with fractional cascading (O(n log n) space, O(log n) time; see Chazelle and Guibas' two papers)
• Preparata's trapezoid tree method (also O(n log n) space, O(log n) time; see paper or Preparata and Shamos' old textbook)
• Persistent search tree method (O(n log n) space, O(log n) time by path copying; see Sarnak and Tarjan's paper, which also reduced space to O(n))
• my notes

Sep 25:

• Planar separator method (O(n) space, O(log n) time; see Lipton and Tarjan's paper)
• Kirkpatrick's hierarchical triangulation method (see paper, or Preparata and Shamos' book, or Iacono's video)
• my notes

Sep 27:

Oct 2:

• Point location in sublogarithmic time (O(n) space, O(loglog U) time; see my paper from '11)
• my notes

Oct 4:

Oct 9, 11: Nonorthogonal range searching.

• Willard's method (O(n) space, O(n^{0.793}) time in 2D, via the ham-sandwich cut theorem; see paper)
• A dual method (O(n^{4.82}) space, O(log n) time in 2D; for duality, see Sec 8.2 of BCKO)
• Clarkson's cutting tree (O(n^{2+eps}) space, O(log n) time in 2D) via the Cutting Lemma (proof by random sampling; see Clarkson's paper)
• my notes

Oct 16, 18:

• Matousek's partition tree (O(n) space, O(n^{1/2+eps}) time in 2D) via the Partition Theorem (proof by multiplicative weights update; see Matousek's paper)
• "Applications" to combinatorial geometry (Szemeredi-Trotter theorem and Erdos' unit distance problem; see Ch4 of Matousek's book)
• Nonlinear range searching (via the linearization technique)
• Multi-level versions of partition trees (see Sec 16.2 of BCKO)
• my notes

Oct 23:

• Halfspace range reporting in 2D and 3D (O(n log n) or O(n loglog n) space, O(log n + k) time; see my paper) via the Shallow Cutting Lemma (see Matousek's paper)
• my notes

Oct 25: Dynamic geometric data structures. Dynamic 2D convex hull.

Oct 30: General dynamization techniques.

• Static to insert-only: The "logarithmic method" (Bentley and Saxe '80)
• Static to fully dynamic: The "square root method" (same paper)
• Static to offline dynamic, via segment tree
• my notes

Nov 1: Dynamic 2D point location.

• Dynamic segment tree (O(log^2 n) query and update time)
• ... with dynamic fractional cascading (O(log n loglog n) query and O(log^2 n) update time)
• Sketch of a version of the latest method by C. and Nekrich'15 (O(log n (loglog n)^2) query and O(log n loglog n) update time)
• my notes

Nov 6, 8: Approximate nearest neighbor search. In constant dimensions.

• Grid method (O(n) space and O(1) time, for fixed radius)
• (Compressed) quadtree method (O(n) space and O(log U) time for decision problem; see Sariel's book)
• ... with shifting (O(n) space and O(log U) time; see Bern'93 and Lemma 3.3 in C.'98)
• Balanced quadtree (O(n) space and O(log n) time; see again the above papers)
• Z-ordering (same result but simplified; see C.'02 and wikipedia, and also a recent paper by C., Har-Peled, and Jones)
• my notes

Nov 13, 15: In high dimensions.

• Dimension reduction via the Johnson-Lindenstrauss Lemma (n^{O((1/eps^2)log(1/eps))} space, O(poly(d)) time for Euclidean distances; see Indyk and Motwani's original paper and also Matousek's survey on metric embedding)
• Locality-sensitive hashing (near O(n^{1+1/c}) space, O(poly(d) n^{1/c}) time for approximation factor c, for Hamming, L_1, and Euclidean distances; see again Indyk and Motwani's original paper and Sec 2.9 of Matousek's notes)
• my notes

Nov 20:

• The L_infinity case: Indyk's search tree method (near O(n^t) space, O(d log n) time for approximation factor O(log_t log d); see paper)
• my notes

Nov 22:

• Offline case: the "polynomial method" (near n^{2-sqrt{eps}} time via matrix multiplication and Chebyshev polynomials; this paper also got near n^{2-eps^{1/3}})
• my notes

Dec 4: Wrap-up. Orthogonal range searching in moderate dimensions.

Dec 7, 11: Student presentation.