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

Summary

In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a simple polygon (not self-intersecting). Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points.
A strictly convex polygon is a convex polygon such that no line contains two of its edges. In a convex polygon, all interior angles are less than or equal to 180 degrees, while in a strictly convex polygon all interior angles are strictly less than 180 degrees.
The following properties of a simple polygon are all equivalent to convexity:
Every internal angle is strictly less than 180 degrees.
Every point on every line segment between two points inside or on the boundary of the polygon remains inside or on the boundary.
The polygon is entirely contained in a closed half-plane defined by each of its edges.
For each edge, the interior points are all on the same side of the line that the edge defines.
The angle at each vertex contains all other vertices in its edges and interior.
The polygon is the convex hull of its edges.
Additional properties of convex polygons include:
The intersection of two convex polygons is a convex polygon.
A convex polygon may be triangulated in linear time through a fan triangulation, consisting in adding diagonals from one vertex to all other vertices.
Helly's theorem: For every collection of at least three convex polygons: if all intersections of all but one polygon are nonempty, then the intersection of all the polygons is nonempty.
Krein–Milman theorem: A convex polygon is the convex hull of its vertices. Thus it is fully defined by the set of its vertices, and one only needs the corners of the polygon to recover the entire polygon shape.
Hyperplane separation theorem: Any two convex polygons with no points in common have a separator line.

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 (29)

Related lectures (80)

Related publications (38)

Related people (6)

Related concepts (16)

Related MOOCs (7)

Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).

Organisé en deux parties, ce cours présente les bases théoriques et pratiques des systèmes d’information géographique, ne nécessitant pas de connaissances préalables en informatique. En suivant cette

Organisé en deux parties, ce cours présente les bases théoriques et pratiques des systèmes d’information géographique, ne nécessitant pas de connaissances préalables en informatique. En suivant cette

Geometry

Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician who works in the field of geometry is called a geometer. Until the 19th century, geometry was almost exclusively devoted to Euclidean geometry, which includes the notions of point, line, plane, distance, angle, surface, and curve, as fundamental concepts.

Minkowski addition

In geometry, the Minkowski sum of two sets of position vectors A and B in Euclidean space is formed by adding each vector in A to each vector in B: The Minkowski difference (also Minkowski subtraction, Minkowski decomposition, or geometric difference) is the corresponding inverse, where produces a set that could be summed with B to recover A. This is defined as the complement of the Minkowski sum of the complement of A with the reflection of B about the origin. This definition allows a symmetrical relationship between the Minkowski sum and difference.

Simple polygon

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, they are piecewise-linear Jordan curves consisting of finitely many line segments. They include as special cases the convex polygons, star-shaped polygons, and monotone polygons. The sum of external angles of a simple polygon is . Every simple polygon with sides can be triangulated by of its diagonals, and by the art gallery theorem its interior is visible from some of its vertices.

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

CH-353: Introduction to electronic structure methods

Repetition of the basic concepts of quantum mechanics and main numerical algorithms used for practical implementions. Basic principles of electronic structure methods:Hartree-Fock, many body perturbat

Convex Functions

Covers the properties and operations of convex functions.

Regular Polyhedra: Definitions and Symmetries

Explores the definitions and symmetries of regular polyhedra, focusing on the five known convex regular polyhedra from ancient times.

Geodesic Convexity: Theory and Applications

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

Martin Jaggi, Sebastian Urban Stich, Amirkeivan Mohtashami

It has been experimentally observed that the efficiency of distributed training with stochastic gradient (SGD) depends decisively on the batch size and—in asynchronous implementations—on the gradient staleness. Especially, it has been observed that the spe ...

2021, ,

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

2021Ola Nils Anders Svensson, Lars Rohwedder

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bound ...