By SecondThread, history, 4 years 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!

Feel free to post any questions below!

• +145

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