I was looking for a fun geometry problem to solve and came across the closest pair of points problem.
The problem statement is:
Given a set of points, in 2D, compute the closest pair of points.
The brute force algorithm takes time. There’s a better solution described at the Wikipedia page Closest pair of points problem, which takes time.
As far as I know, there aren’t any posted solutions using OpenCL to compute the closest pair. So I’ve implemented one, it’s posted at closest-pair.
There are a few challenges in adapting the algorithm for OpenCL. Namely, we can’t use recursion so we must convert the recursive algorithm to a procedural one. In this case it’s not to complicated because the structure of the solution is easily converted from the top-down recursive algorithm to a bottom-up parallel algorithm. There are some tricky issues when the number of points are not a power of 2. I’ve commented the code for those cases.