Kissing Polytopes
Copyright policy )Kissing Polytopes
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 distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching lower and upper bounds on this distance and discuss its exact computation. We also give similar bounds in the case of disjoint rational polytopes whose binary encoding length is prescribed.
28 pages, 3 figures
- McMaster University Canada
- McMaster University (McMaster Centre for Software Certification) Canada
- Brown University United States
- Paris 13 University France
- Technion – Israel Institute of Technology Israel
Geometric constructions in real or complex geometry, Metric Geometry (math.MG), pyramidal width, lattice polytopes, Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry), Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.), distances in geometric lattices, facial distance, Mathematics - Metric Geometry, Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry), Optimization and Control (math.OC), vertex-facet distance, alternating projections, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Optimization and Control
Geometric constructions in real or complex geometry, Metric Geometry (math.MG), pyramidal width, lattice polytopes, Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry), Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.), distances in geometric lattices, facial distance, Mathematics - Metric Geometry, Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry), Optimization and Control (math.OC), vertex-facet distance, alternating projections, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Optimization and Control
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!