Validate general position of the input

[barakugav]

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

[efifogel]

From a practical point of view, wasting ~n^2 just on checking doesn't make sense. In CGAL you have the following: 1. CGAL_assertion()---enabled by default only in DEBUG mode 2. CGAL_expenssive_assertion()---disabled by default ____ _ ____ _ /_____/_) 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 <#19>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNODYZUK4QUI2V25JPRLWW5PFLANCNFSM6AAAAAAUYTRAQA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>