You are wrong. The best case is O(n), not O(n log n). Just take a triangle and put a bunch of points inside it. That will be O(n). The best case is not where it is divided evenly. It is where all points are inside the triangle (see 1:20) meaning you don't need to do any more work. This is not quicksort. There is a big difference. In quicksort, all elements, on both sides of the partition, must be processed eventually, so it is best to divide them evenly. Here there are basically 3 partitions per recursion: two of them get processed recursively, one gets ignored. So naturally, the best case maximizes the number of points ignored. Somehow I could not find an explanation of this on the internet. I look on stack overflow, and there are several professional software engineers, claiming the best case is O(n log n). It's kind of sad, because the best case of O(n) is kind of glaringly obvious. It's like people have a pathological inability to accept that this is a different algorithm from quicksort, and when it comes to analysis they just completely shut down their brains and assume it's just like quicksort, even though about 15 seconds of thinking will tell you otherwise. The best case doesn't even really matter, it just really disturbs me to see so many people completely lack critical thinking. This video has 17 thousand views over the course of 4 years, and I'm the first one to comment this? I'm not very smart. But at least I actually tried to analyze this instead of just mentally copy-pasting the quicksort analysis.
