# AlgorithmsThread Episode 7: All Point Pairs

Hi everyone! I just published Episode 7 of AlgorithmsThread, which talks about processing all pairs of points, while keeping the rest of the points sorted in a helpful way. I talk about the following problems in it:

- Biggest Triangle in a set of points
- Smallest Triangle in a set of points
- Number of pairs of non-intersecting triangles
- Minimum Area Quadrilateral in a set of points

I find this to be a really helpful trick that isn't super well known, so feel free to check it out if any of these sound like things you want to learn!

## Problem Links:

Feel free to post any questions below!

Thanks for sharing the gem.

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).What are the etymologies of the names "Algorithms Dead" and "AlgorithmsThread"?

Also, wanted to add that I watched some of this video and thought it was well-presented! I liked how you explained the motivation behind some of the ideas & used drawing extensively. What software/hardware are you using for the drawing? (I assume you're using OBS for the recording?)

Derived from Algorithms Live and his handle name I guess.

Oh cool, thanks! I hadn't heard of Algorithms Live before, but I see the connection now. :P

Yep, originally it was Algorithms Dead as a pun on Algorithms Live. Then I changed it to AlgorithmsThread because that sounds a bit cooler I think.

SecondDead would be cooler

Here's another good problem on this technique: 1019D - Large Triangle

I wrote up an explanation of that problem here: https://codeforces.com/blog/entry/61144

What about just comparison between two points and not three/four (Like finding the min euclidean dist in a set of points). Would this work even if more than 2 points can be collinear? Maybe you can do the rotating vector trick and find the shortest distance on the collinear line for each vector?

Side question: Is the number of possible edges (and thus vectors you have to check) the triangular number? https://oeis.org/A000217

Yes, the number of pairs of points is a triangular number, since it is nChoose2. I think there is a closest pair of points algorithm that runs on n*log(n) time. You can also just run Delaney Triangulation and check all O(n) of the edges after that too, which is also n*log(n).

Thanks for the quick reply. That makes sense and I'll look into those algorithms you mentioned.

There's a much simpler divide and conquer algorithm, you can get more information along with a c++ implementation here.