Digital Media Services | Events

Motivation: Halving lines and levels in arrangements; Lower envelopes and Davenport-Schinzel sequences

Davenport-Schinzel sequences of order 3 – upper and lower bounds

Realization of Davenport-Schinzel sequences of order 3 as lower envelopes of segments; Algorithms for constructing lower envelopes; Arrangements of curves

A single cell in an arrangement of curves; The consistency lemma; Zones in arrangements of curves and in arrangements of lines

Algorithms for constructing a single cell; The combination lemma

Randomized incremental algorithms for constructing a single cell and the entire arrangement; Backwards analysis

Randomized incremental algorithms for constructing a single cell and the entire arrangement, and backwards analysis (continued); The Clarkson-Shor technique and its applications

Analysis of randomized incremental algorithms via the Clarkson-Shor technique; Complexity of envelopes of segments and curves in the plane via Clarkson-Shor; Union of pseudo-disks – combinatorics and algorithms

Lower envelopes in three dimensions; Zones in arrangements of planes in three dimensions

Zones in three dimensions (continued); Overlays of lower envelopes in three dimensions; Random sampling – Range spaces and VC-dimension

Random sampling (continued); Epsilon-approximations and epsilon-nets; Geometric applications; Decomposition of arrangements by cuttings

Incidences between points and lines; The crossing lemma and Szekely’s method; Range searching