Questions tagged [convex-geometry]
A branch of geometry dealing with convex sets and functions. Polytopes, convex bodies, discrete geometry, linear programming, antimatroids, ...
1,008
questions
17
votes
1
answer
521
views
Does the boundary of a convex body contain a regular planar pentagon?
How to prove or disprove that the boundary of any convex body in $\mathbb{R}^3$ includes 5 points which form a regular planar pentagon? The following consideration suggests the answer "yes": if we ...
7
votes
1
answer
435
views
Is an infinite-dimensional "Lebesgue measure" uniquely determined by a set of positive finite measure?
Let $\mu$ be a probability measure on a subset $C \subset \mathbb{R}^\infty$ of the space of sequences, and assume, for simplicity, that $C$ is closed and convex.
We say that $\mu$ admits shifts if ...
0
votes
2
answers
3k
views
Determine the boundary points of a set of points [closed]
I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$?
There are methods like convex hull, concave hull and $\...
1
vote
0
answers
450
views
About the $C^{1,1} $regularity of the boundary of a set
I am studying a paper that uses the following property :
Consider $U$ and $V$ open, bounded and convex domains in $R^n$ with $U \supset \overline{V}$ and suppose that $min_{y \in V} |x - y| = \lambda ...
20
votes
4
answers
910
views
The limit of edge-midpoint convex polyhedra
Starting with a convex polyhedron $P_1 \subset \mathbb{R}^3$,
replace that with $P_2$, the convex hull of the midpoints of the edges of $P_1$.
Continuing this process, we obtain a ...
0
votes
1
answer
316
views
About the regularity of the boundary of a set
Consider $\Omega_1, \Omega_2$ two convex, bounded domains in $R^n$ with $\Omega_1 \supset \overline{\Omega_2}$ and suppose that $\operatorname{dist}(x, \partial \Omega_2) =\min_{y \in \partial \...
3
votes
2
answers
209
views
A lower bound on $\|\cdot\|_{p_{\ast}}$ image of $\ell^{q_{\ast}}$ vectors
The motivation for this question comes from this paper where we study lower bounds on the complexity of convex optimization algorithms (BTW, if you find a better title for my question, please let me ...
2
votes
0
answers
104
views
Regularity of the Minkowski functionnal of a convex
Let $K$ be a convex compact set in $\mathbb{R}^2$ with $0 \in \overset{\circ}{K}$. The Minkowski functional associated to K is:
\begin{align*}
\varphi_K(x):= \inf \left\{t>0 \; : \; tx \in K \...
4
votes
2
answers
971
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$ ...
8
votes
1
answer
217
views
Translative packing constant strictly larger than lattice packing constant
Simply put, my question is this: what is the smallest dimension, if any,
where we can know for sure that a convex body exists whose translative
packing constant is strictly larger than its lattice ...
2
votes
1
answer
165
views
Distance from constant width bodies
EDIT As @David has observed, my conjecture was clearly wrong for $\ n:=2.\ $ Let me still give it a chance for $\ n\ge 3$.
I'll call a family $\ F\ $ of bound closed convex subsets of $\ \mathbb R^n\ ...
4
votes
0
answers
214
views
Circumscribing simplex to convex body?
Q.
Does every (perhaps smooth) compact convex body $K$ in $\mathbb{R}^d$ admit a
circumscribing simplex, each facet of which touches (shares a point with) $K$?
How about a circumscribing regular ...
2
votes
1
answer
336
views
Chebyshev centres of a bounded closed convex set in a strictly convex Banach space
Suppose $X$ is a strictly convex Banach space. Does there exist a bounded closed convex set $K$ in $X$ such that the set of all Chebyshev centers $C(K)$ of $K$ is a proper subset of $K$ with diameter ...
3
votes
0
answers
67
views
Polynomials connected with Gale's condition and cyclic polytopes
I was reading about cyclic polytopes and (I think naturally) became interested in polynomials $f(X) \in \mathbb{R}[X]$ which have a factorization of the form $f(X)=g(X)g(X+1)$ for some $g(X) \in \...
4
votes
1
answer
668
views
$\mathcal{H}$-polyhedron under a linear map
Let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a (bounded) polyhedron for $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, $n,m > 0$.
Moreover, let $M \colon \mathbb{R}^n \to \...
6
votes
5
answers
854
views
Approaching convex and discrete geometry from other disciplines
I would like to learn some convex and discrete geometry (number 52 in MSC2010). I thought that it would be interesting to approach it from some other parts of mathematics - either by learning ...
3
votes
0
answers
553
views
Linear transformation of a polyhedral cone
Let $C$ be a polyhedral cone in $\mathbb{R}^m$ with H- and V-representations
$C = \{x : A x \le 0 \} = \{R y : y \ge 0\}.$
The pair $(A,R)$ is referred to as a double description (DD) pair of the ...
6
votes
2
answers
955
views
When does a cone contain its dual cone?
Let $V$ be a finite-dimensional vector space with an inner-product $(,)$ and let $C\subset V$ be a cone in $V$. Let $C^\vee$ denote the dual of $C$ with respect to $(,)$, i.e., the set of vector $v\in ...
1
vote
2
answers
661
views
Volume of normal cone of a simplex (at a vertex)
This question is related to an orthant-type simplex in $\mathbb{R}^n$, which can be defined as
$$ S = \{x\in\mathbb{R}_{+}^n: \sum_{i=1}^nx_i \leq 1\}=\overline{\mbox{conv}}(0,e_1,\ldots,e_n). $$
For ...
2
votes
1
answer
418
views
intersection of the unit cube and a hyperplane containing the main diagonal
Let $A$ be a linear $m$-dimensional subspace of $\mathbf{R}^n$ $m < n$, containing the point $(1,1,\ldots,1) \in \mathbf{R}^n$,
and consider the intersection of $A$ and the unit cube $\Delta_n$ (...
3
votes
0
answers
74
views
Minimax-like theorems involving union and intersection of regions in $\mathbb R^d$
From Minimax theorems, we roughly know that if $f(x,y)$ is convex on $X$ and concave $Y$ for both compact $X,Y$, then:
$$
\max_{x\in X}\min_{y\in Y} f(x,y)=\min_{y\in Y}\max_{x\in X} f(x,y).
$$
We can ...
5
votes
1
answer
489
views
The number of facets of a polyhedron under linear transformation
Consider a (not necessarily bounded) convex polyhedron $P\subset \mathbb{R}^n$ which has $k$ facets.
Let $L:\mathbb{R}^n \to \mathbb{R}^m$ be a linear transformation.
Question1: Is there a fixed ...
9
votes
1
answer
3k
views
Linear transformation of a polyhedron
Is there a simple proof that shows:
Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of
finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron.
Minkowski sum of ...
2
votes
1
answer
138
views
Volume of a polytope with relaxed constraints
Consider a polytope in $n$ dimensions defined by a set of linear constraints:
$$P = \{x \in \mathbb{R}^n : Ax \leq b\}$$
where A is some $m \times n$ constraint matrix, and $b = (b_1,\ldots,b_m)$ is ...
4
votes
1
answer
405
views
Characterization of $l_p$ up to a linear isometry
There is a science called "Geometry of Banach spaces". I wonder if they managed to give a geometric characterization of $\ell_p$ ($p\in[1,\infty]$) up to isometric isomorphism (among all Banach spaces)...
10
votes
2
answers
656
views
Status of Barany's conjecture?
One of Barany's most intriguing conjectures is about the $f$-vectors of convex polytopes. It asks:
Let $P$ be a convex $d$-polytope. Is it always true that $f_k \geq \min(f_0, f_{d-1})$?
A convex $...
3
votes
0
answers
140
views
Covering fat objects with fat objects
The family of rectangles has the cover property, i.e.:
For every $R\geq 1$, $k\geq 1$: every rectangle with aspect ratio $kR$ can be exactly covered by $\lceil k\rceil$ (possibly overlapping) ...
13
votes
0
answers
405
views
Surface area of convex hull [duplicate]
Let Q be the convex hull of a non-convex polyhedron P. Is it true that the surface area of Q is not greater than the surface area of P?
3
votes
0
answers
340
views
Convex functions with non-singular hessian measure are continuously differentiable?
It is known that every convex function $f: \Omega\to \mathbb{R}$, $\Omega$ convex subset of $\mathbb{R}^n$, has a weak derivative of bounded variation $Df\in BV_{loc}(\mathbb{R}^n)$ (e.g. Evans and ...
3
votes
0
answers
181
views
A question on Hilbert geometries as metric-measure spaces
Recall that a Hilbert geometry is the interior of a convex body $K \subset \mathbb{R}^n$ provided with the metric
$$
d(x,y) = \frac{1}{2} \ln\left(\frac{|x-b|}{|y-b|}\frac{|y-a|}{|x-a|}\right) ,
$$
...
1
vote
1
answer
262
views
Vertices of Curves and Eigenvectors of Hessian
This might be a trivial question, but I can't seem to figure it out. Suppose I have an implicitly defined curve in the plane given by $f(x,y) = t$.
This curve is strictly convex, and feel free to ...
1
vote
1
answer
145
views
extreme points of the image of a nonlinear vector-valued function
Consider a continuous function $f : D \rightarrow \mathbb{R}^m$, where $D \subseteq \mathbb{R}^n$ is a compact convex set. I am in search of a result that helps me say something about the extreme ...
6
votes
2
answers
404
views
Triangulations of special polyhedra
Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...
6
votes
2
answers
408
views
Random walk in a convex body or convex polytope
Let $\Delta$ be a convex body (i.e. a compact convex subset) or a convex polytope in
$\mathbb{R}^n$. Let $x$ be a point inside $\Delta$ and consider a (uniform) random walk starting at $x$ inside $\...
3
votes
1
answer
283
views
Generalization of notion of convexity
I am searching for the correct term for the following, if it exists.
A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius $...
22
votes
5
answers
1k
views
Is the diameter of a centrally symmetric convex body realized by a pair of antipodal points?
Let $S \subset \mathbb{R}^n$ be the boundary of a centrally symmetric convex body and provide $S$ with the geodesic metric given by its embedding in Euclidean space (i.e., the distance between two ...
9
votes
0
answers
775
views
Isoperimetric inequality, isodiametric inequality, hyperplane conjecture... what are the inequalities of this kind known or conjectured?
I duplicate here a question I asked on math.stackexchange.
Question: Which inequalities similar to the famous isoperimetric inequality is known?
conjectured?
I recently learned about some ...
3
votes
2
answers
286
views
Perimeter of a 'trapped' convex set
Consider the following setup: three bounded, 'nice' convex sets $A \subseteq B \subsetneq C \subset \mathbb{R}^2$, and three points $x,y,z\in \partial A\cap \partial B\cap \partial C$ (see edit below)....
2
votes
0
answers
111
views
Quickly checking an inequality on a convex region
I previously posted this question to math.sx at: https://math.stackexchange.com/questions/748015/quickly-checking-if-an-inequality-holds-on-a-convex-region but I'm thinking that MO may be more ...
5
votes
2
answers
164
views
Computational complexity of deciding isomorphism of rational polyhedral cones
Let $C,C'$ be rational polyhedral cones in $\mathbb R^n$ both with non-empty interior. Rational means they are generated by vectors with rational entries. One says that $C,C'$ are isomorphic if there ...
3
votes
0
answers
107
views
Decomposing a cone based on decompositions of its facets
Let $C$ be a cone in $\mathbb{R}^d$, and let $x_1, \dots, x_k$ be its extreme rays. Suppose that the $x_i$ satisfy:
For all $i, j$, $\langle x_i, x_j \rangle \ge 0$,
There is a partition $A \cup B = ...
1
vote
0
answers
88
views
Tubular neighbourhood which is nowhere piecewise linear
I recently asked this question.
I think, if the following were true, then I would solve my problem.
Let $E\subset\{(x_1,\dots,x_n)\in\mathbb R^n\;|\;x_i\geq 0\, \&\, \sum_ix_i=1\}$ be a convex ...
9
votes
0
answers
360
views
An affine invariant of convex bodies
The following invariants of "pointed" convex bodies (i.e., pairs consisting of a convex body and a distinguished point in its interior) roughly measure how many of its linear images fit between the ...
3
votes
0
answers
156
views
Intrinsic volumes of a family of convex sets $\{K_n\}$
Consider a family of convex sets $\{K_n\}$ such that $K_n \subset \mathbb{R}^n$ for each $n$. The kinds of sets one might be considering could be, for instance,
$K_n$ is the cube of side $2A$, i.e., ...
6
votes
1
answer
495
views
References to proofs of a theorem by Van Kampen-Flores
Theorem (Van Kampen-Flores 1930s) From any 7 points in four-dimensional space one can choose two disjoint triples such that the triangles with vertices at the triples intersect each other.
This ...
6
votes
0
answers
158
views
Norms and distributions
Question 1. Is there a nice or explicit way to describe the class of all distributions (generalized functions) $\mu$ on the $n$-sphere $S^n \subset \mathbb{R}^{n+1}$ for which the function
$$
F(v) := \...
2
votes
1
answer
269
views
Homotopy with non piece-wise linear boundary
in the middle of a long proof I encounter the following problem.
Let $E$ be a closed and convex set in $\mathbb R^n$ such that for all $\vec x\in E$ it holds that $\sum_ix_i=1$. (We can understand $E$...
5
votes
4
answers
859
views
Probability that convex hull of multivariate Gaussian sample contains a given point
I am generating random vectors $X_1, \dots, X_N$ from a $d$-dimensional multivariate normal $\text N(\mu, \Sigma)$. I would like to know what is the probability that a given point $y \in R^d$ falls ...
11
votes
2
answers
970
views
Triangle with largest perimeter in a convex region
What is the largest value of $r$ such that the following statement is always true?
"Let $C$ be a convex region with area $1$. There must exist a triangle contained in $C$ whose perimeter is at least ...
4
votes
2
answers
199
views
The maximal discrete parallelepiped in a convex body
Does the positive constant $c_d$, depending only from dimension, with the following property exist?
Property:
for every convex body $K\subset \mathbb R^d$ there exists parallelepiped $P\subset K$ ...