What's a O(n^2 log ⁡n) algorithm that decides if a distinct set is completely triangulable?

Asked May 18 '16 at 11:34

Active May 18 '16 at 11:34

Viewed 44 times

Let P be a finite set of n distinct points in ℝ2. The set P is called completely triangulable if for any three points p,q,r∈P the area of their triangle is always positive.

An algorithm that determines if a finite set P is completely triangulable returns TRUE if PP is completely triangulable and FALSE otherwise.

What is an algorithm that runs in O(n^2 log ⁡n) time?

My thinking is to use breadth first search but the running time of it is O(n^2), so how can I edit that to achieve O(n^2 log n)?

asked May 18 '16 at 11:34

tictactoe

Why would you want to achieve `O(n^2 log n)` if you can find a solution that runs in `O(n^2)`? Also elaborate on how you'd use BFS in this situation. – Glubus May 18 '16 at 11:44
1

I don't see how you fit BFS in this situation. – T. Claverie May 18 '16 at 12:14
Can you please explain what is the meaning of `the area of their triangle is always positive` ? – webNeat May 18 '16 at 12:31
I assumed it should be strictly greater than 0, but yes I would definitely like to know the answer. – T. Claverie May 18 '16 at 12:53

What's a O(n^2 log ⁡n) algorithm that decides if a distinct set is completely triangulable?

0 Answers0