Problems Base course RU

Built on

points

Articles

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 ML Algorithm k-means Splits points into k groups so that points sit close to the centre of their group. O(n · k · d) per step 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

Problems

Clusters on a map of epicentres Do the segments cross How many triangles Lloyd's algorithm by the rules Pairs closer than r The area inside the fence A navigator without trigonometry A pick-up point Lap time The density threshold The farthest pair The two closest towns Where to put a new station

Often together

classic 6 geodata 5 interviews 4 nearest neighbour 3 randomized 3 polygon 3 hashing 2 maps and navigation 2 contests 2 science and physics 2 clustering 2 analytics 2