geodata

Articles

GRA Algorithm Heavy paths Path queries on trees: heavy paths cut any path into O(log n) array stretches under a segment tree. O(log² n) per query 1 problem DP Technique Knuth and divide-and-conquer optimisations 45 thousand towns on a map by population class: 3.5 million evaluations instead of five billion, because the best split is monotone. O(k · n log n) 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems PAR Algorithm Closest pair of points The two nearest of n points in n log n: a cut, a strip 2d wide and seven neighbours; with a grid, n on average. O(n log n) 2 problems GEO Technique Vectors and orientation The sign of the cross product is a left or right turn; almost all of computational geometry stands on it. O(1) per turn 2 problems GEO Algorithm Convex hull The smallest convex polygon containing all the points, in O(n log n). O(n log n) 2 problems GEO Algorithm Delaunay triangulation and Voronoi diagram Zones of the nearest point and triangles with empty circles: two sides of one structure. O(n log n) on average 2 problems NUM~ Algorithm Gradient descent Finds the minimum of a function by steps against the gradient, in the direction of steepest descent. O(κ · log(1/ε)) steps 2 problems ML Algorithm DBSCAN Gathers dense regions of points of any shape into clusters and marks lone points as noise. O(n·Q + Σ|N(p)|) 2 problems TEC Technique Coordinate compression Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks. O(n log n) to compress 2 problems

Problems

Clusters on a map of epicentres How many triangles Pairs closer than r Seismic watch The area inside the fence A navigator without trigonometry Channels without interference How many people in a rectangle The density threshold The two closest towns Town codes Where to put a new station Flood watch

Often together

classic 7 contests 6 interviews 5 points 5 science and physics 4 optimization 3 nearest neighbour 3 polygon 3 range queries 2 divide and conquer 2 approximation 2 randomized 2