|
|
Interesting idea. It's extremely easy to come up with counterexamples, but I wanted to see how it runs on random sets, so I implemented and tested it. I was afraid that contestants might be trying to pull something like that out in problems that require an "honest" convex hull solution and I'm happy that's not the case, even on random cases. On the other hand, in real world applications, 1% error rate might be acceptable.
I used 167 sets of 20000 random points (x,y from 0 to 30000).
The right answer was returned in 58.7% of cases.
The answer differed from the right answer by 0.28% on average.
The algorithm stopped after 3.13 iterations on average.
Another set consisted of 2665 cases, 2000 random points each in the same range of coordinates.
The right answer was returned in 52.1% of cases.
The answer differed from the right answer by 1.11% on average.
The algorithm stopped after 3.07 iterations on average.
edit: some more data: 1299 cases, 10^5 random points each in the same range of coordinates.
The right answer was returned in 51.1% of cases.
The answer differed from the right answer by 0.17% on average.
The algorithm stopped after 3.08 iterations on average. |
