Star Simulation

We know we can't compare every star to every other, this is too slow. The line about "no more than 100,000 being within k of each other" is a big hint. Just break our "universe" up into KxKxK sized chunks. We only need to check points that are in the sectors within K of us. This is at max 8 sectors. The distribution requirements ensure that not every point compares against most other points (This has to do with the fact that only 400 points clustered tightly make 100,000 "pairs" of points (400^2/2 = 100k). So we can expect on average only 400 comparisons per point, which puts us at 40 million.

Dividing space up so that you can find only the subset of problems you need to solve is a very common technique. It is used in one of the convex hull algorithms.