# Questions tagged [convex-geometry]

The tag has no usage guidance.

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
201 views

• 12k
356 views

### Approximating the diameter of a convex set defined by semidefinite constraints

A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations. Now, if you want to minimize a linear ...
267 views

### Intersection of Hamming Balls

I am interested in the volume of the intersection of two Hamming balls of radius say m/6 in m-dimensional space, the distance between whose centers is about \sqrt{m}. I would ideally like this to be a ...
• 51
83 views

### Enforcing general position in $2d$ linear programming

Let $(x_1, y_1), ..., (x_k, y_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$. I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear ...
• 1,143
124 views

### Equivalence of weighted Minkowski sums

Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices. Furthermore, consider a variant of the Minkowski sum (somehow ...
189 views

### Computing the convex hull of several polyhedra

Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities. How easy is it to compute an ...
• 1,224
149 views

### Is the following problem in $coNP$?

Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$? At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
• 12.8k
1 vote
41 views

### Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"

I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
1 vote
69 views

### How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?

I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
• 119
1 vote
16 views

• 425
32 views

### doubt about volume packing lemma for intersection of convex sets and lattices (repost from math SE)

Lemma 3.24 of Additive Combinatorics by Tao and Vu states the following: Let $\Gamma \subset \mathbb{R}^d$ be a lattice of full rank, let $V$ be a bounded open subset of $\mathbb{R}^d$, and let $P$ ...
• 91
An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints $Ex + Fy = g, y\geq 0$ in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real matrices ...