### SecondThread's blog

By SecondThread, history, 9 months ago,

# 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!

• +145

 » 9 months ago, # |   +8 Thanks for sharing the gem.
 » 9 months ago, # |   0 Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
 » 9 months ago, # |   0 What are the etymologies of the names "Algorithms Dead" and "AlgorithmsThread"?
•  » » 9 months ago, # ^ |   +10 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?)
•  » » 9 months ago, # ^ |   +10 Derived from Algorithms Live and his handle name I guess.
•  » » » 9 months ago, # ^ |   0 Oh cool, thanks! I hadn't heard of Algorithms Live before, but I see the connection now. :P
•  » » » 9 months ago, # ^ |   0 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.
•  » » » » 3 months ago, # ^ |   -8 SecondDead would be cooler
 » 9 months ago, # |   +9 Here's another good problem on this technique: 1019D - Large TriangleI wrote up an explanation of that problem here: https://codeforces.com/blog/entry/61144
 » 3 months ago, # |   0 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
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 3 months ago, # ^ |   0 Thanks for the quick reply. That makes sense and I'll look into those algorithms you mentioned.
•  » » » 3 months ago, # ^ |   0 There's a much simpler divide and conquer algorithm, you can get more information along with a c++ implementation here.