we’ve done a lot of really neat algos in geo lately. I only have 5 mins so I briefly summarize.

I really like that the algorithms are simple and have really cool randomized analysis.

1. closest pair in linear time!

first we give an approx algo: choose a random point, search for his NN, grid based on that distance. Toss points which are isolated at this granularity of grid.

With probability \(1/2\) we kill \(1/2\) the points at least. So this is short. And closest pair is not become isolated until we’re basically at the right distance.

Now for actual closest pair once we have this approximation guarantee what we do is also grid and then there aren’t allowed to be too many points in a ball around each point by virtue of our lower bound on shortest distance.

2. given \(n\) points count the number of points above each line connecting two of the points. There is a neat \(n^2\) time solution using arrangements. Here is an \(n^2\log n\) solution due to Peter. Algo is just, for each point sort other points by angle and itterate over the points in this sorted order.

3. all nearest neighbors in linear time!

you create increasingly larger circles around each point. you increment the grid granualarity. The neat part is that you use “backwards analysis” (i.e., thinking about how many points I am NN to) to bound run time.

4. exact LP in constant dimensions in linear time

add constraints in a random order. keep track of where opt is. if constraint doesn’t invalidate opt keep opt. else: search over the line intersection points with the new line you added for the new opt.

pr that \(i\)-th added line invalidates opt is at most \(d/i\) where \(d\) is the dimension.

expected time is hence \(O(n)\).