SecondThread's blog

AlgorithmsThread 7: All Point Pairs
By SecondThread, history, 4 years ago, In English

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!

  • Vote: I like it
  • +145
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for sharing the gem.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the etymologies of the names "Algorithms Dead" and "AlgorithmsThread"?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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?)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Derived from Algorithms Live and his handle name I guess.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply