CS 598 TMC, Fall 2019

Geometric Data Structures

Instructor

Meeting Time and Place

Course Overview

• 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%
  • Homework 1 (due Sep 27, Fri)
  • Homework 2 (due Oct 18, Fri)
  • Homework 3 (due Nov 13, Wed)
  • Homework 4 (due Dec 4, Wed)
• 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.)

See guidelines for presentation and project.

References

• [BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications (3rd ed.), Springer-Verlag, 2008
• [GRT] J. Goodman, J. O'Rourke, and C. D. Toth (eds.), Handbook of Discrete and Computational Geometry (3rd ed.), CRC Press, 2017

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:

• Random sampling method (O(n) space, O(log n) time; see Clarkson and Shor's original paper or Mulmuley's book)
• Randomized incremental method (see Ch6 of BKCO)
• my notes

Oct 2:

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

Oct 4:

• Point location in sublogarithmic time: general case (O(n) space, O(log n/loglog n) or O(sqrt{log U/loglog U}) time; see my '09 paper with Patrascu)
• my notes

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)
• Time/space tradeoffs
• "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.

• Insert-only (O(log n) update and O(log n) query time, by Preparata'79)
• Fully dynamic: the hull tree method (O(log^2 n) update and O(log n) query time, by Overmars and van Leeuwen'80; see also Preparata and Shamos' book)
• my notes

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.

• Offline case: lop-sided range trees (n^{2-1/O~(c)} time for d = c log n; see Impagliazzo et al. and the appendix of my paper)
• Online case: randomized lop-sided range trees (my SoCG'17 paper)
• Offline case again: the polynomial method (n^{2-1/O(log c)} time for d = c log n; see Abboud, Williams, and Yu)
• my notes

Dec 7, 11: Student presentation.