All Questions
Tagged with convexity convex-polytopes
43 questions
0
votes
1
answer
113
views
On the extreme points of two convex sets
Let $A$ and $B$ be two compact convex sets (which may be assumed to be polytopes) in $\mathbb R^n$ such that $A\cap B\ne\emptyset$. Is it then always true that either $A\cap\text{ext}B\ne\emptyset$ ...
- 128k
4
votes
1
answer
159
views
Approximation of convex bodies by polytopes corresponding to smooth toric varieties
Let $P\subset \mathbb{R}^n$ be an $n$-dimensional polytope with rational vertices. There is a well known construction which produces an $n$-dimensional algebraic variety $X_P$ called toric variety. In ...
- 21.8k
2
votes
1
answer
308
views
Intersection of the simplex with a linear subspace of codimension $2$
The sets are defined in $\mathbb{R}_+^n$ $(n\geq 1)$. The relative interior of a convex set $C$ is denoted $\mathring C$.
Let $S$ be the $n$-simplex:
$$S=\left\{x\in\mathbb{R}_+^n,\,\sum_{i=1}^n x_i=1\...
- 449
1
vote
1
answer
119
views
Volume ratio of polytopes with few vertices
The volume ratio of a convex body $K\subset \mathbb{R}^{n}$ is $v_r(K) = \inf_{\mathcal{E}\subset K} \left(\frac{Vol(K)}{Vol(\mathcal{E})}\right)^{1/n}$ where the infimum run over ellipsoids included ...
- 245
0
votes
0
answers
146
views
Graduate level convexity - Intersection of an r-polytope with a hyperplane is an r-1 polytope
I am trying to follow Roger Webster's Convexity 's proof of Euler's celebrated result on the relationship between the number of faces of a polytope. An image of the proof is here.
In the course of the ...
- 121
1
vote
0
answers
65
views
Minimum bounding rectangle of symmetric convex bodies in the plane : is the ball the worst case
The minimal rectangle containing the euclidean ball in the plane is the standard cube $B_\infty = [-1;1]^2$. I would like to know if the euclidean ball is the worst symmetric convex body to be ...
- 245
2
votes
0
answers
61
views
Does absolute retract imply convex structure?
In the theory of selection, it is known that any compact absolute retract (AR) carries a convexity structure defined by E. Michael. It is also known that a convex structure
developed by Van de Vel ...
- 2,083
4
votes
1
answer
290
views
Intrinsic definition of a cone in a normal fan
Let $P\subseteq \mathbb{R}^n$ be a full dimensional polytope. Let us assume that $P$ has a facet description with the following inequalities:
$$ \left<x,u_F\right> \geq -a_F$$
where $u_F\in \...
- 1,889
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
4
votes
0
answers
367
views
On intrinsic volumes
Let $\Gamma$ be a convex polytope in $\mathbb R^n$. The $k$-th intrinsic volume of $\Gamma$ is the number
$$
\text{v}_k(\Gamma)=\sum_{\Delta\in{\mathcal B}(\Gamma,k)}\text{vol}_k(\Delta)\psi_\Gamma(\...
- 311
1
vote
0
answers
120
views
John's ellipsoid of a polytope
Suppose that $X$ is $\mathbb R^n$ with some polyhedral norm, that is, the unit ball of $X$ is an $n$-dimensional polytope. Assume that the John ellipsoid of $X$ is an Euclidean ball that touches every ...
- 113
3
votes
1
answer
258
views
Polygon of convex arcs
Convex polygons in the plane $R^2$ arise in linear programming where the constraints are linear. The objective linear function attains its maximum at a vertex of the feasible region(if exists).
Assume ...
- 422
5
votes
2
answers
320
views
Convex hull with genus information
Are there convexity generalizations that admit genus information?
For example in genus $1$ is there a way to think of this polyhedron as convex while this polyhedron as non-convex? Any two points can ...
- 13.9k
2
votes
0
answers
385
views
(Quasi) convexity of separately convex homogeneous functions
Consider a function $f:\mathbb{R}^n_{\geq 0}\rightarrow \mathbb{R}$ that is separately convex, i.e. such that $\frac{d^2f}{dx_i^2}\geq 0$ for all $i\in \{1,\dots n\}$. Assume also that $f$ is ...
- 389
1
vote
0
answers
368
views
Convex hull of the intersection of nonconvex sets
I have a set $D$ in $\mathbb{R}^{d+1}$ which is the intersection of $d$ domains $D_i$ given by $f(x_{i}) \leq x_{i+1} \leq g(x_{i})$ for two functions $f$ and $g$.
I want to find the convex hull of $...
- 31
3
votes
1
answer
151
views
The center of a minimal convex superbody
Is the following true?
CONJECTURE: $\,$ Let $\ B\ C\subseteq\mathbb R^n\ $ be convex bodies in $\mathbb R^n$ such that $\ C\ $ is centrally symmetric, $\ B\subseteq C,\ $ and $\ t\!\cdot\! B\ $ cannot ...
- 7,500
2
votes
1
answer
248
views
Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?
This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
- 4,049
1
vote
0
answers
59
views
Conditions on probability measure that generates non-void random polytope
Let $C$ be a non-void compact convex set in $\mathbb{R}^d$, and $\nu$ a probability measure on $C$. Then under what conditions on $C$ and $\nu$, the following statement is true: If $X_1,\cdots,X_{d+1}$...
- 599
1
vote
1
answer
193
views
What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?
I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely,
$X \in \mathbb{R}^{...
- 13
0
votes
0
answers
62
views
Looking for a homogeneous function with some properties
I'm looking for a 1-homogeneous function $\pi \colon \mathbb{R}^n_{\geq 0} \to \mathbb{R}$ satisfying the following properties:
1) $\pi$ is not concave. This is equivalent to the fact that there ...
- 357
5
votes
1
answer
384
views
Examples of Polyhedra with Large Shadows
Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
- 321
4
votes
2
answers
981
views
Convex Sets and Nearest Neighbors
For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is unique. It is known that $c(x) = s$ ...
- 177
1
vote
0
answers
126
views
Convex Optimization related problem
Suppose two non-negative convex functions $f$ and $g$ be given.
We want to solve the following optimization
$$\max_{g\leq\epsilon}f.$$
Now suppose that both $f$ and $g$ can be upper-bounded by a ...
- 1,109
8
votes
0
answers
826
views
Geometry of the metric cone
Let us say that two metrics $d$ and $d_0$ on a set $X$ are related if there exist positive constants $0 < \alpha \leq \beta$ such that
$$
\alpha \,\left(d_0(x,y) + d_0(y,z) - d_0(x,z)\right) \leq
...
- 13.5k
4
votes
1
answer
316
views
A construction related to scissors congruence
I was thinking about the following some time ago. My question is whether such things have been studied before.
Let $E_n$ be the abelian group with a generator for each (bounded) euclidean polytope of ...
- 55.9k
4
votes
1
answer
250
views
Zoll Flat Finsler tori and convex bodies on a starry night
The starry night. The "celestial sphere" is given by set of non-zero vectors in $\mathbb{R}^n$ modulo positive dilations (i.e., $v \equiv w$ if $v = \lambda w$ for some $ \lambda > 0$) and the "...
- 13.5k
1
vote
2
answers
431
views
Higher dimensional convex hull
Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as $E(v)=...
user33954
3
votes
0
answers
188
views
Covering points with a convex hull
Consider a set of $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$, for some $n \gg d$. Suppose $\{x_1,\ldots,x_n\} \subset C \subset \mathbb{R}^d$. Say that a set of points $y_1,\ldots,y_m \in C$ covers $...
- 794
2
votes
0
answers
51
views
Conditions under which a set of points have a low weight representation under some basis
Let $S \subset R^d$ be a convex polytope in $d$ dimensional real space. Say that $S$ has weight $w$ if there exists some basis $x_1,\ldots,x_d$ such that for every point $v \in S$, we can write $v = \...
- 794
5
votes
1
answer
387
views
Extreme rays in the cone of (semi)metrics
How many extreme rays are there on the polytopal cone formed by all semimetrics on a set with $n$ elements?
Some background. Given a set $X$ with $n$ elements, the set of all semimetrics
$d:X \times ...
- 13.5k
2
votes
2
answers
1k
views
Convex upper bound on a linear-fractional function
I have a function of the form $f(x,y) = \frac{x}{c+y}$ where $c$ is a positive constant, $c \ge x \ge 0$, and $y \ge 0$. I would like to find a convex upper-bound for this function. Is there a ...
- 362
16
votes
2
answers
3k
views
Approximating a convex function by a piecewise linear function
Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow \...
- 161
1
vote
1
answer
2k
views
Question regard checking convexity by "restriction to any line that intersects the function domain"
Hello all,
I have a question (probably stupid one) about the fact that " A function is convex if and only if it is convex when restricted to any line that intersects its domain".
In Stephen Boyd and ...
- 43
2
votes
1
answer
2k
views
Proving that a specific function is quasiconvex
Hello all,
Assume we have a sequence of quasiconcave functions (in $X$) denoted by $f_{i,j}(X)$ for $i,j = 1,\ldots,n$. Denote by $F(X)$ the $n\times n$ matrix whose $(i,j)$ entry is the function $f_{...
- 43
16
votes
2
answers
5k
views
Weighted area of a Voronoi cell
Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
- 195
4
votes
2
answers
1k
views
Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center
Does this already exist in literature? The closest Ive been able to find is circumscribe intersection of two ellipsoids with a common center by W. Kahan (http://www.cs.berkeley.edu/~wkahan/Ellipint....
- 263
45
votes
4
answers
5k
views
Polynomial roots and convexity
A couple of years ago, I came up with the following question, to which I have no answer to this day. I have asked a few people about this, most of my teachers and some friends, but no one had ever ...
2
votes
3
answers
596
views
a different algebra/representation for convex sets
Hi,
I was dealing with finding a feasible region for a set of norm inequalities and the feasible region is convex. The question is not about how to find the feasible region but how to represent the ...
- 21
16
votes
5
answers
1k
views
A characterization of convexity
While doing some research on polytopes I came to the following question. Maybe it's already somewhere but anyway I'll post it here.
Let $X\subset \mathbb{R}^3$ be such that, for every plane $P$, $P\...
- 1,001
8
votes
1
answer
556
views
A variation on "Hearing the shape of a drum" for polytopes.
Let $\varphi:\mathcal S^{d-1}\longrightarrow \mathbb R_{>0}$ be a strictly positive function describing the boundary $\varphi(\mathbf x)\mathbf x,\mathbf x\in\mathbb S^{d-1}$ of a $d-$dimensional ...
- 17.9k
7
votes
2
answers
1k
views
Maximal Ellipsoid
John's Theorem can be stated as "To every compact, convex body, there is a unique inscribed ellipsoid, whose volume is maximal among all inscribed ellipsoids." It goes on to classify this maximal ...
- 1,588
4
votes
1
answer
363
views
Efficiently sampling points from an integer lattice.
Let $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denote the set of integer points in the positive orthant of the $\ell_1$ ball of radius $m$, where $m < n$. For each $x \in \mathcal{L}$, let ...
- 41
34
votes
16
answers
7k
views
Generalizations of the Birkhoff-von Neumann Theorem
The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.
The question is to point out different ...
- 24.7k