Left click on the canvas to apply the current action

In geometry, the convex hull of a given set is the smallest convex set containing it. In the field of geometric algorithms, the convex hull of a finite set of points is very often used. In this case, the envelope is a convex polygon.

Following the strategy of any incremental algorithm, this algorithm
construct the convex hull of *n* points from the convex hull
of *n - 1*points.
Given a convex polygon (which is the convex hull of *n - 1* points)
and a point outside the polygon, the algorithm adds the new point as a
vertex of the frontier of the new convex hull.

The algorithm proceeds as follows. First, sort the points lexicographically.
Then proceed iteratively: given a point *p _{i}* and the convex
hull

This technique consists in subdividing recursively the problem in smaller subproblems, solve them and then merge the solutions of the subproblems to get the solution of the original problem.

In the case of the convex hull, the algorithm does the following operations. First orders the points lexicographically, like in the incremental algorithm.

Then, the recurrence starts. The algorithm divides the set *S* of
the input points into to subsets *S _{a}* and

The convex hull *CH _{a}* and

In order to merge the two convex hulls and obtain the convex hull of the set *S*,
the algorithm computes the common exterior tangents between *CH _{a}* and

This technique is also known as the gift wrapping. It consists in polygonize the set of points in a certain order and, as the polygonization progresses, gradually remove any "pockets" that may form, that is, the sub-polygons of the convex hull that are not part of the polygonization of the points that are being generated.

More specifically, first a point *p* is selected from the given set *S*,
that it is certainly a point of the convex hull, taking, for example, the lexicographically
minor point.
Then, the rest of the points are ordered angularly from *p*.
After that, the algorithm proceeds iteratively processing every point with the
given order, and keeps at every step the convex hull of the points considered so far.
For it, at the *i-nth* iteration, the algorithm part from the convex hull
*CH _{i-1}* of the points

The Halton sequences are very useful for generating random points on the plane
(actually pseudo-random). This sequences are constructed with a deterministic
method based on the coprime numbers. An example of constructing point in the
square *(0,1) X (0,1) ⊂ ℝ ^{2}* with bases 2 and 3,
respectively, is as follows:

To generate the sequence of base 2, the space (0,1) is divided recursively in two halves, then four parts, then eight parts, etc.

*1/2, 1/4, 3/4, 1/8, 5/8, 1/16, 9/16, ...*

Similraly, in base 3 the interval *(0,1)* is recursively divided
into thirds, obtaining the sequence:

*1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 1/27, ...*

Combining both sequences the following points are obtained in the square
*(0,1) X (0,1)*:

*(1/2,1/3), (1/4,2/3), (3/4,1/9), (1/8,4/9), (5/8, 7/9)
(3/8,2/9), (1/16,5/9), (9/16,1/27), ...*