Open barakugav opened 1 year ago
From a practical point of view, wasting ~n^2 just on checking doesn't make sense. In CGAL you have the following:
//) o /__ // (__ ( ( ( (/ (/-(-'(/ /
On Sat, 11 Feb 2023 at 11:58, Barak Ugav @.***> wrote:
The algorithm assume general position of the input, namely no more than two points on the same line. There is a function checking that this is the case, but its not always enabled, as it runs in O(n^3). We can check it in O(n^2) using duality, and run the function always, without damaging the O(n^2 log n) runtime
— Reply to this email directly, view it on GitHub https://github.com/barakugav/FDML/issues/19, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABVBNODYZUK4QUI2V25JPRLWW5PFLANCNFSM6AAAAAAUYTRAQA . You are receiving this because you are subscribed to this thread.Message ID: @.***>
The algorithm assume general position of the input, namely no more than two points on the same line. There is a function checking that this is the case, but its not always enabled, as it runs in O(n^3). We can check it in O(n^2) using duality, and run the function always, without damaging the O(n^2 log n) runtime