**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

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.

Related courses (3)

Related lectures (23)

Related publications (47)

Related people (11)

Related units (2)

Related concepts (3)

MGT-418: Convex optimization

This course introduces the theory and application of modern convex optimization from an engineering perspective.

MATH-476: Optimal transport

The first part is devoted to Monge and Kantorovitch problems, discussing the existence and the properties of the optimal plan. The second part introduces the Wasserstein distance on measures and devel

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees

In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example from linear in the size of the input to quadratic in the size of the input, analyses that take the output size explicitly into account can produce better runtime bounds that differentiate algorithms that would otherwise have identical asymptotic complexity.

In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set of points, in 2- or 3-dimensional space. The algorithm takes time, where is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an algorithm (Graham scan, for example) with Jarvis march (), in order to obtain an optimal time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick–Seidel algorithm, and it naturally extends to 3-dimensional space.

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact.

Geodesic Convexity: Theory and Applications

Explores geodesic convexity in metric spaces and its applications, discussing properties and the stability of inequalities.

Convex Sets: MGT-418 Lecture

On Convex Optimization covers course organization, mathematical optimization problems, solution concepts, and optimization methods.

Duality in Linear Programming

Explores the concept of duality in linear programming, discussing the relationship between primal and dual problems.

Aude Billard, Diego Felipe Paez Granados, David Julian Gonon

This paper describes a novel method for non-holonomic robots of convex shape to avoid imminent collisions with moving obstacles. The method's purpose is to assist navigation in crowds by correcting steering from the robot's path planner or driver. We evalu ...

2021, ,

A convex parameterization of internally stabilizing controllers is fundamental for many controller synthesis procedures. The celebrated Youla parameterization relies on a doubly coprime factorization of the system, while the recent system-level and input-o ...

2021Carl Johan Peter Johansson, Riccardo Tione

In this paper, we study the rank-one convex hull of a differential inclusion associated to entropy solutions of a hyperbolic system of conservation laws. This was introduced in [B. Kirchheim, S. Muller and V. S(sic)ver & aacute;k, Studying Nonlinear PDE by ...