All Questions
1,545 questions
88
votes
2
answers
7k
views
68
votes
2
answers
2k
views
Continuous maps which send intervals of $\mathbb{R}$ to convex subsets of $\mathbb{R}^2$
Let $f : \mathbb{R} \longrightarrow \mathbb{R}^2$ be a continuous map which sends any interval $I \subseteq \mathbb{R}$ to a convex subset $f(I)$ of $\mathbb{R}^2$. Is it true that there must be a ...
- 629
64
votes
6
answers
5k
views
Shortest closed curve to inspect a sphere
Let $S$ be a sphere in $\mathbb{R}^3$. Let $C$ be a closed curve in $\mathbb{R}^3$ disjoint from and
exterior to $S$
which has the property that every point $x$ on $S$ is visible to some point $y$ of $...
- 151k
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 ...
44
votes
11
answers
26k
views
Algorithm for finding the volume of a convex polytope
It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
- 441
41
votes
6
answers
2k
views
Approximating a convex disk by an ellipse
For every convex compact set $K$ of area $1$ in $\mathbb{R}^2$, among all ellipses of area $1$ there exists an ellipse $E$ such that the area of the symmetric difference between $K$ and $E$ is ...
- 7,276
40
votes
2
answers
2k
views
Abstract definition of convex set
I'd like to formulate an abstract definition of convex sets: a set $K$ is convex if it is endowed with a ternary operation $K\times[0,1]\times K\to K$, written $(x:t:y)$, satisfying axioms
$(x:0:y)=(...
- 2,519
39
votes
2
answers
2k
views
How to make a sandwich from just one piece of bread?
I don't know how to go about such questions. It's not exactly my area, so maybe it is stupid, but curiosity is winning.
So I have a piece of bread $P$ of a really non-regular shape (let's make it ...
- 5,529
38
votes
7
answers
5k
views
Shortest path connecting two opposite points on a cube
Is it true, that a path connecting two opposite points (i.e. such that the segment joining them passes through the centre of mass of the cube) on the surface of the $d$-dimensional unit cube (with $d&...
- 1,431
38
votes
0
answers
1k
views
Converse of the Archimedean property of the sphere
In his remarkable book On the Sphere and Cylinder, where he came tantalizingly close to discovering calculus, Archimedes showed that the area of the portion of the sphere contained between a pair of ...
- 7,149
36
votes
0
answers
1k
views
Two-convexity ⇒ Lefschetz?
Assume that
$\Omega$ is an open simply connected set in $\mathbb R^n$
(two-convexity) if 3 faces of a 3-simplex belong to $\Omega$ then whole simplex in $\Omega$.
Is it true that any component of ...
- 45k
35
votes
6
answers
6k
views
How to explain the concentration-of-measure phenomenon intuitively?
One way to phrase the
"concentration-of-measure"
phenomenon is that,
for a Euclidean sphere $S^d$ in $d$ dimensions, for large $d$,
"most of the mass is close to the equator, for any equator."1
Q. ...
- 151k
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
35
votes
1
answer
2k
views
Which polygons can be turned inside out by a smooth deformation?
Take a non-degenerate polygon with side lengths $\{a_1,\dots,a_n\}$ in a convex configuration. What is the condition on the $a_i$'s so that the polygon can be turned inside out by a continuous motion ...
- 4,862
33
votes
3
answers
2k
views
Polar body of a convex body that avoids a lattice
Let $K \subset {\bf R}^d$ be a symmetric convex body (an open bounded convex neighbourhood of the origin with $K = -K$) with the property that $K + {\bf Z}^d \neq {\bf R}^d$, i.e. the projection of $K$...
- 114k
31
votes
2
answers
2k
views
The logic of convex sets
Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
- 33.8k
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
28
votes
2
answers
1k
views
Can we always shift two disjoint convex bodies a little bit to decrease the volume of their convex hull?
Let $K,L\subset\mathbb R^d$ be two disjoint compact convex sets with non-empty interiors. Can $x=0$ be a point of local minimum for the function $F(x)=\text{vol}_d(\text{conv(K,L+x))}$?
I was asked ...
- 61.9k
28
votes
1
answer
1k
views
Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)
This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
- 2,585
28
votes
0
answers
546
views
Can every 3-dimensional convex body be trapped in a tetrahedral cage?
Can every 3-dimensional convex body be trapped in a tetrahedral cage?
Although the question is fairly unambiguous, I give all relevant definitions:
$\bullet$ A subset $C$ of $\mathbb{R}^n$ is an $n$-...
- 7,276
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
26
votes
4
answers
3k
views
Analogy of Parseval identity for Legendre Transform ?
Parseval's identity states that the sum of squares of coefficients of the Fourier transform of a function equals the integral of the square of the function, or
$$ \sum_{-\infty}^{\infty} |c_n|^2 = (1/...
- 4,462
26
votes
3
answers
1k
views
Largest possible volume of the convex hull of a curve of unit length
What is the largest possible volume of the convex hull of an open/closed curve of unit length in $\mathbb{R}^3$?
- 6,819
26
votes
3
answers
3k
views
Research trends in geometry of numbers?
Geometry of numbers was initiated by Hermann Minkowski roughly a hundred years ago. At its heart is the relation between lattices (the group, not the poset) and convex bodies. One of its fundamental ...
- 907
25
votes
4
answers
1k
views
Do random projections (approximately) preserve convexity?
The Johnson-Lindenstrauss lemma implies that any set of $k$ points in $\mathbb{R}^d$ can be randomly projected into $d' \approx \log(k)/\epsilon^2$ dimensions such that the distances between each pair ...
- 253
25
votes
4
answers
3k
views
Ellipse naturally associated with a polygon
My colleagues and I have stumbled onto a way to associate an ellipse, or equivalently a positive definite symmetric matrix, to a polygon that is different from other better known ways. We want to know ...
- 27.5k
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 363
25
votes
3
answers
2k
views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 33.8k
24
votes
3
answers
1k
views
Average measure of intersection of a convex region with its translate
Let $\lambda$ denote the Lebesgue-measure on $\mathbb{R}^n$, and let $C\subset\mathbb{R}^n$ be a convex region.
My question is about
$$f(C):=\int_{C} \lambda(C \cap (x + C) ) \mathrm{d} x.$$
How ...
- 343
24
votes
1
answer
1k
views
Which natural numbers are a square minus a sum of two squares?
Question: Which natural numbers are of the form $a^2 - b^2 - c^2$ with $a>b+c$?
This question came up in (Eike Hertel, Christian Richter, Tiling Convex Polygons with Congruent Equilateral ...
- 25.5k
24
votes
1
answer
546
views
What is the minimal volume of the intersection of a self-dual cone and the unit ball?
When thinking of some other problem, I stumbled upon the following innocently looking question that is natural enough to have been considered (and, possibly, solved) many years ago. However my ...
- 61.9k
23
votes
2
answers
2k
views
Structures of the space of neural networks
A neural network can be considered as a function
$$\mathbf{R}^m\to\mathbf{R}^n\quad
\text{by}\quad x\mapsto w_N\sigma(h_{N-1}+w_{N-1}\sigma(\dotso h_2+w_2\sigma(h_1+w_1 x)\dotso)),$$
where the $w_i$ ...
- 333
23
votes
1
answer
713
views
Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks
Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...
- 7,149
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 ...
- 1,303
22
votes
2
answers
1k
views
Do the elementary properties of mixed volume characterize it uniquely?
Background
Take 2 convex sets in $\mathbb{R}^2$, or 3 convex sets in $\mathbb{R}^3$, or generally, $n$ convex sets in $\mathbb{R}^n$. "Mixed volume" assigns to such a family $A_1, \ldots, A_n$ a ...
- 27.7k
21
votes
5
answers
1k
views
Is there a midsphere theorem for 4-polytopes?
The (remarkable) midsphere theorem says that each combinatorial
type of convex polyhedron may be realized by one all of whose edges are
tangent to a sphere
(and the realization is unique if the center ...
- 151k
21
votes
2
answers
1k
views
On convergence of convex bodies
Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$.
Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any $0<\...
- 21.8k
20
votes
4
answers
950
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 ...
- 151k
20
votes
2
answers
922
views
A functional inequality about log-concave functions
Let $f,g$ be smooth even log-concave functions on $\mathbb{R}^{n}$, i.e.,$f=e^{-F(x)}, g=e^{-G(x)}$ for some even convex functions $F(x),G(x)$. Is it true that:
$$
\int_{\mathbb{R}^{n}} \langle \...
- 3,946
20
votes
0
answers
433
views
Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?
Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...
- 13.6k
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
19
votes
3
answers
2k
views
Cutting convex sets
Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference.
Can one cut every bounded convex set of the Euclidean plane into an arbitrary number $...
- 17.9k
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
19
votes
1
answer
1k
views
Where to find some subset of Khovanskii's 15 proofs of the BKK theorem?
(I asked this question on MSE, but someone suggested it would be better asked here.)
I'm a fan of the Bernstein-Khovanskii-Kushnirenko theorem (that the number of solutions in $(\mathbb{C}^*)^n$ to a ...
- 453
19
votes
0
answers
551
views
Talagrand's "Creating convexity" conjecture
We say a subset $A$ of $\mathbb{R}^N$ is balanced if
\begin{equation}
x \in A, \lambda \in [-1,1] \implies \lambda x \in A.
\end{equation}
Given a subset $A$ of $\mathbb{R}^N$, we write
\begin{...
- 484
19
votes
0
answers
641
views
Is there a simpler proof of the key lemma in the paper by Hiroshi Iriyeh and Masataka Shibata on the 3D Mahler conjecture?
In this remarkable paper 30 pages are occupied by the proof of the following innocently looking lemma:
Let $K$ be an origin-symmetric convex body in $\mathbb R^3$. There exist three planes through ...
- 61.9k
18
votes
2
answers
840
views
Reference to a conjecture on unit vectors in Euclidean space
I have heard that there exists the following conjecture (if I am not mistaken).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists another unit vector ...
- 21.8k
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
18
votes
3
answers
997
views
Convex functions in convex sets
Suppose $\Omega \subset \mathbb{R}^n$ is some bounded, convex set. For which domains $\Omega$ is it true that for every convex function $f:\Omega \rightarrow \mathbb{R}$ the average of the function in ...
18
votes
3
answers
2k
views
Are the Platonic solids shadows of 4-polytopes?
Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection).
I am wondering if each of the five ...
- 151k