Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Convex hull algorithms
Summary
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.
In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities.
Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and sometimes also in terms of h, the number of points on the convex hull.
Consider the general case when the input to the algorithm is a finite unordered set of points on a Cartesian plane. An important special case, in which the points are given in the order of traversal of a simple polygon's boundary, is described later in a separate subsection.
If not all points are on the same line, then their convex hull is a convex polygon whose vertices are some of the points in the input set. Its most common representation is the list of its vertices ordered along its boundary clockwise or counterclockwise. In some applications it is convenient to represent a convex polygon as an intersection of a set of half-planes.
For a finite set of points in the plane the lower bound on the computational complexity of finding the convex hull represented as a convex polygon is easily shown to be the same as for sorting using the following reduction. For the set numbers to sort consider the set of points in the plane. Since they lie on a parabola, which is a convex curve it is easy to see that the vertices of the convex hull, when traversed along the boundary, produce the sorted order of the numbers . Clearly, linear time is required for the described transformation of numbers into points and then extracting their sorted order. Therefore, in the general case the convex hull of n points cannot be computed more quickly than sorting.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.