Lecture

2D Case: Polynomial Encroaching

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

This lecture covers the 2D case of polynomial encroaching, focusing on assumptions about facets containing integer points, piece integer hulls, and vertices of polyhedra. The instructor explains the concept of polynomial encroaching of A and b.

Official source

Related concepts (32)

Polyhedron

In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is a polyhedron that bounds a convex set. Every convex polyhedron can be constructed as the convex hull of its vertices, and for every finite set of points, not all on the same plane, the convex hull is a convex polyhedron. Cubes and pyramids are examples of convex polyhedra. A polyhedron is a 3-dimensional example of a polytope, a more general concept in any number of dimensions.

List of uniform polyhedra

In geometry, a uniform polyhedron is a polyhedron which has regular polygons as faces and is vertex-transitive (transitive on its vertices, isogonal, i.e. there is an isometry mapping any vertex onto any other). It follows that all vertices are congruent, and the polyhedron has a high degree of reflectional and rotational symmetry. Uniform polyhedra can be divided between convex forms with convex regular polygon faces and star forms. Star forms have either regular star polygon faces or vertex figures or both.

Uniform star polyhedron

In geometry, a uniform star polyhedron is a self-intersecting uniform polyhedron. They are also sometimes called nonconvex polyhedra to imply self-intersecting. Each polyhedron can contain either star polygon faces, star polygon vertex figures, or both. The complete set of 57 nonprismatic uniform star polyhedra includes the 4 regular ones, called the Kepler–Poinsot polyhedra, 5 quasiregular ones, and 48 semiregular ones. There are also two infinite sets of uniform star prisms and uniform star antiprisms.

Semiregular polyhedron

In geometry, the term semiregular polyhedron (or semiregular polytope) is used variously by different authors. In its original definition, it is a polyhedron with regular polygonal faces, and a symmetry group which is transitive on its vertices; today, this is more commonly referred to as a uniform polyhedron (this follows from Thorold Gosset's 1900 definition of the more general semiregular polytope). These polyhedra include: The thirteen Archimedean solids.

Icosahedron

In geometry, an icosahedron (ˌaɪkɒsəˈhiːdrən,-kə-,-koʊ- or aɪˌkɒsəˈhiːdrən) is a polyhedron with 20 faces. The name comes . The plural can be either "icosahedra" (-drə) or "icosahedrons". There are infinitely many non-similar shapes of icosahedra, some of them being more symmetrical than others. The best known is the (convex, non-stellated) regular icosahedron—one of the Platonic solids—whose faces are 20 equilateral triangles. There are two objects, one convex and one nonconvex, that can both be called regular icosahedra.

Related lectures (17)

Faces, Facets and Vertices

Covers the concepts of faces, facets, and vertices in polyhedra, exploring minimal faces and inequalities.

Separating Hyperplanes: Theory and Applications

Explores separating hyperplanes for two sets X and Y, discussing conditions for separation and implications of convexity.

Regular Polyhedra: Definitions and Symmetries

Explores the definitions and symmetries of regular polyhedra, shedding light on ancient geometry and modern mathematical formalization.

Shadows: Proper and Cast Shadows in Descriptive Geometry

Covers proper and cast shadows in descriptive geometry with practical examples and exercises.

Regular Polyhedra: Definitions and Symmetries Log in to Mediaspace to watch this video