3 ms·
Thanks! The algorithm is based on Clarkson's incremental convex hull algorithm and runs in O(n^ceil(d/2) + n log(n)). I am planning on eventually adding a spe
by 33a 12y ago
Thanks! The algorithm is based on Clarkson's incremental convex hull algorithm and runs in O(n^ceil(d/2) + n log(n)). I am planning on eventually adding a special case for d=2 to use a sweep line method, which is faster in practice.
Also note that all internal computations are performed using exact arithmetic based on Shewchuk's filtered predicates.