bq. Given a set $S$ of $n$ points and a query point $p$, find the point in $S$ closest to $p$.

For uniformly distributed points, a good strategy is to represent the space as a grid and maintain a list of inner points for each cell. For a given query point, we can check the cell the point falls into and its neighbouring cells. For a $sqrt(n) * sqrt(n)$ grid we’ll have one point per cell, on average. On average, finding the point in $S$ closest to $p$, requires traversing a constant number of cells.

For uniformly distributed points, a good strategy is to represent the space as a grid and maintain a list of inner points for each cell. For a given query point, we can check the cell the point falls into and its neighbouring cells. For a $sqrt(n) * sqrt(n)$ grid we’ll have one point per cell, on average. So, on average, finding the point in $S$ closest to $p$, requires traversing a constant number of cells.

h2. Longest common subsequence solution