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.
Here's another good problem on this technique: 1019D - Large Triangle
I wrote up an explanation of that problem here: https://mirror.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).
There's a much simpler divide and conquer algorithm, you can get more information along with a c++ implementation here.