Finding two items from an array

Accelerated Computing CUDA CUDA Programming and Performance
1

Hi,
I have a large array containing points in a 2D plane. I want to select two such points which are farthest from each other. How can i achieve that using numba cuda.

Thanks,

2

I don’t have a complete answer for you. A naive method would be to do an all-pairs comparison, this scales by O(N^2) and would be similar conceptually to an all-pairs force calculation in an n-body problem, for example.

Doing a quick google search, I think you can find discussions of “more efficient” methods, one of which appears to be to reorder your points in the form of a convex hull, and then perform an operation on that (perhaps “rotating calipers”).

Whether this is easily parallelizable, I don’t know. I think if you decompose the work in the convex hull and rotating calipers, you may be able to find portions of the work that are readily parallelizable (embarrassingly parallel) or subject to parallel algorithms like reduction.

I acknowledge this is not a complete-ready-to-go answer. Others may have better suggestions. If you search on “parallel convex hull” or “parallel rotating calipers” or just add “gpu” keyword to your searches, you may find useful material. Here is an example search, it seems to have candidates that may be interesting for further exporation.

3

I say up front that I have never worked on this issue. It seems that in many cases, one should be able to eliminate a lot of candidates by pre-processing using some simple parallel reductions:

(1) Determine the min, max values of each of the x, y components, recording the points at which these occur, similar to isamax in BLAS1. The four extremal points found (xa, ymin; xb, ymax; xmin, yc; xmax, yd) define a quadrilateral. Any point inside this quadrilateral cannot be part of the solution.

(2) For each 2D-point in the array determine whether it is inside the quadrilateral by the cross-product method and mark it accordingly.

(3) Use stream compaction to remove all points interior to the quadrilateral.

After this determine the convex hull of the remaining points. I do not know how to do this efficiently in parallel, check the literature.

4

I don’t know but can dynamic parallelism help in this situation. Although numba doesn’t support it.

5

I don’t now. Maybe. My standard problem-solving process:

(1) Think. Think some more. Now repeat.
(2) Search the literature, thoroughly.