Randomised Incremental Algorithm

The randomized incremental algorithm is an important algorithm in computational geometry. It does not require high theoretical knowledge, has low algorithm time complexity and has a wide range of applications.

The idea of the Incremental Algorithm is similar to the first mathematical induction method. Its essence is to reduce a problem into sub-problems that are just one level smaller in size. Join the current object after solving the sub-problem. Written recursively it is:

T(n) = T(n-1) + g(n)

It is simple in form and can be applied to many geometry problems.

Incremental methods are often combined with randomisation to avoid worst-case scenarios.