Randomization yields simple O(n log star n) algorithms for difficult Omega(n) problems

Olivier Devillers

We use here the results on the influence graph by Boissonnat et al. to adapt them for particular cases where additional information is available. In some cases, it is possible to i…