118 citations · 220 across the 30 of their papers we have counts for
30 papers
Flat simplices and kissing polytopes
Antoine Deza, Lionel Pournin
We consider how flat a lattice simplex contained in the hypercube can be. This question is related to the notion of kissing polytopes: two lattice polytopes contained in…
Kissing polytopes in dimension 3
Antoine Deza, Zhongyuan Liu, Lionel Pournin
It is shown that the smallest possible distance between two disjoint lattice polytopes contained in the cube is exactly for…
Geometry of Sparsity-Inducing Norms
Jean-Philippe Chancelier, Michel de Lara, Antoine Deza +1
Sparse optimization seeks an optimal solution with few nonzero entries. To achieve this, it is common to add to the criterion a penalty term proportional to the -norm, whic…
Small kissing polytopes
Antoine Deza, Zhongyuan Liu, Lionel Pournin
A lattice -polytope is the convex hull of a set of points in whose coordinates are integers ranging between and . We consider the smallest possible dis…
Deep sections of the hypercube
Lionel Pournin
Consider a non-negative number and a hyperplane of whose distance to the center of the hypercube is . If is equal to and is orthogon…
The expansion of half-integral polytopes
Jean Cardinal, Lionel Pournin
The expansion of a polytope is an important parameter for the analysis of the random walks on its graph. A conjecture of Mihai and Vazirani states that all -polytopes have exp…
Counting geodesics between surface triangulations
Hugo Parlier, Lionel Pournin
Given a surface equipped with a set of marked points, we consider the triangulations of with vertex set . The flip-graph of whose vertices are these triangulatio…
Many equiprojective polytopes
Théophile Buffière, Lionel Pournin
A -dimensional polytope is -equiprojective when the projection of along any line that is not parallel to a facet of is a polygon with vertices. In 1968, Geoff…
Kissing polytopes
Antoine Deza, Shmuel Onn, Sebastian Pokutta +1
We investigate the following question: how close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal d…
The rotation distance of brooms
Jean Cardinal, Lionel Pournin, Mario Valencia-Pabon
The associahedron of a graph has the property that its vertices can be thought of as the search trees on and its edges as the rotations between two search…
Sizing the White Whale
Antoine Deza, Mingfei Hao, Lionel Pournin
We propose a computational, convex hull free framework that takes advantage of the combinatorial structure of a zonotope, as for example its symmetry group, to orbitwise generate a…
The complexity of geometric scaling
Antoine Deza, Sebastian Pokutta, Lionel Pournin
Geometric scaling, introduced by Schulz and Weismantel in 2002, solves the integer optimization problem by means of primal au…
Local extrema for hypercube sections
Lionel Pournin
Consider the hyperplanes at a fixed distance from the center of the hypercube . Significant attention has been given to determining the hyperplanes among these suc…
Diameter estimates for graph associahedra
Jean Cardinal, Lionel Pournin, Mario Valencia-Pabon
Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph encodes the combinatorics…
Strong convexity in flip-graphs
Lionel Pournin, Zili Wang
The set of triangulations of a surface with a prescribed set of vertices can be endowed with a graph structure called a flip-graph, whose edges connect t…
Shallow sections of the hypercube
Lionel Pournin
Consider a -dimensional closed ball whose center coincides with that of the hypercube . Pick the radius of in such a way that the vertices of the hypercube are…
Polytopal balls arising in optimization
Antoine Deza, Jean-Baptiste Hiriart-Urruty, Lionel Pournin
We study a family of polytopes and their duals, that appear in various optimization problems as the unit balls for certain norms. These two families interpolate between the hypercu…
Primitive point packing
Antoine Deza, Lionel Pournin
A point in the -dimensional integer lattice is primitive when its coordinates are relatively prime. Two primitive points are multiples of one another when they ar…
A linear optimization oracle for zonotope computation
Antoine Deza, Lionel Pournin
A class of counting problems ask for the number of regions of a central hyperplane arrangement. By duality, this is the same as counting the vertices of a zonotope. We give several…
The diameter of lattice zonotopes
Antoine Deza, Lionel Pournin, Noriyoshi Sukegawa
We establish sharp asymptotic estimates for the diameter of primitive zonotopes when their dimension is fixed. We also prove that, for infinitely many integers , the largest pos…
Elementary moves on lattice polytopes
Julien David, Lionel Pournin, Rado Rakotonarivo
We introduce a graph structure on Euclidean polytopes. The vertices of this graph are the -dimensional polytopes contained in and its edges connect any two polyto…
Diameter, decomposability, and Minkowski sums of polytopes
Antoine Deza, Lionel Pournin
We investigate how the Minkowski sum of two polytopes affects their graph and, in particular, their diameter. We show that the diameter of the Minkowski sum is bounded below by the…
Eccentricities in the flip-graphs of convex polygons
Lionel Pournin
The flip-graph of a convex polygon is the graph whose vertices are the triangulations of and whose edges correspond to flips between them. The eccentricity of a triangulati…
Improved bounds on the diameter of lattice polytopes
Antoine Deza, Lionel Pournin
We show that the largest possible diameter of a -dimensional polytope whose vertices have integer coordinates ranging between and is at most $kd-\lceil2d/3\rcei…