All Questions
1,544 questions
8
votes
1
answer
223
views
Convex hulls of compact sets in a 2-manifold
Let $(\mathbb{R}^2,g)$ be a complete Riemannian manifold. Let $K\subset \mathbb{R}^2$ be a compact, connected set, and let $\text{conv}(K)$ be its convex hull, i.e., the intersection of all ...
- 381
1
vote
0
answers
96
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
1
vote
1
answer
104
views
abstract description of the topology on a real vector space defined by the algebraically open sets
Let $V$ be a real vector space. Given a subset $A \subseteq V$, say that a point $x \in A$ lies in the algebraic interior of $A$ if every affine line $\ell$ that passes through $x$ has the property ...
- 331
2
votes
1
answer
83
views
On equipartitions of surfaces of 3D convex regions
Let S be the surface of a 3D convex region (a 'convex surface'). Let S' be a subset of S. We shall refer to S' as geodetically convex in S if the following condition holds: If A and B are two points ...
- 5,979
4
votes
0
answers
128
views
Can a convex frame hold all circles of radius $1/n$ immobile?
Here is a frame that holds circles of radius $1, \frac{1}{2}, \frac13, ..., \frac17$ immobile.
By "immobile", I mean no circle can move without overlapping other circles or the frame, ...
- 3,507
1
vote
0
answers
335
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 988
0
votes
1
answer
55
views
On 'axiality' of planar convex regions
Axiality has been studied under a definition given here: https://en.wikipedia.org/wiki/Axiality_(geometry)
Consider an alternative definition of axiality as follows: For a convex region C, consider a ...
- 5,979
1
vote
1
answer
169
views
Best projection on non-convex discrete set with two constraints
I want to compute the projection of a vector $\left( x\right) _{1\leq
i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set
$$
S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...
- 47
2
votes
1
answer
84
views
'Constrained morphing' of planar convex regions
Morphing may be defined as a continuous transition of one shape to another. This post is about modifying planar regions continuously from one form to another under some constraints.
Qn: If $C_1$ and $...
- 5,979
1
vote
0
answers
38
views
Possible extensions of the perpendicular axes theorem for moment of inertia
This post continues on Moment of inertia from Bisectors and partitioning lines for convex regions defined with respect to the moment of inertia.
The perpendicular axis theorem states that the moment ...
- 5,979
2
votes
1
answer
61
views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
- 55
1
vote
0
answers
56
views
Bisectors and partitioning lines for convex regions defined with respect to the moment of inertia
Ref: Mathematical Omnibus by Fuchs and Tabachnikov, Lecture 11.
Consider any planar convex region C. A line l on the same plane and cutting thru C may be called an inertia bisector of C if it divides ...
- 5,979
0
votes
0
answers
126
views
Question about symmetric bilinear form and convex geometry
Consider a Finsler norm $\varphi$ in $R^4$, and a positive definite symmetric bilinear form $S$, there also exists a vector-valued symmetric linear form $Q$, such that if $S(v, w) = 0$, then $Q(v, w)$ ...
- 21
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 3
0
votes
0
answers
272
views
Finding the eigenvectors of a submatrix
Let $A=(a_{kl})$ be a matrix in $M_n(\mathbb{R})$ when $n$ is even. Let $B=(b_{kl})$ be the symmetric $2n$ by $2n$ matrix whose entries are given by,
$b_{k,l}=a_{kl}$ if $1\leq k,l\leq n$.
$b_{n+k,l}=...
- 4,058
2
votes
0
answers
202
views
Geometric inequality related with convexity of the boundary
I'm new to Mathoverflow, so hopefully my question is well-posed.
My problem states as follows:
Let $\Omega\subset\mathbb{R}^n$ be a bounded Lipschitz domain with boundary $\partial \Omega$ , $\delta&...
- 21
0
votes
0
answers
79
views
Number of tiles inside a region of a hyperbolic tiling
Let $\mathbb{D}$ be the Poincare disc model of hyperbolic geometry with $\{p,q\}$ tiling on it.
In this, paper authors calculated the number of tiles on any circular region centered at a vertex or ...
- 613
1
vote
0
answers
47
views
Nash Equilibria change linearly in (some) game parameters. Already known / follows from a more general result?
EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)
Question: Is the following result already known? Or is it a ...
4
votes
0
answers
158
views
On moments of inertia of planar and 3D convex bodies
The following observation can be readily proved using the perpendicular axes theorem and intermediate value theorem: "Given any planar figure C, through any point on it, there is at least one ...
- 5,979
4
votes
0
answers
117
views
Writing the $\ell^{p/(p-1)}$ unit sphere as a semi-algebraic set for $p\in\Bbb N$
The $\ell^p$ unit sphere $\{x\in\Bbb R^n\mid |x_1|^p+\cdots+|x_n|^p=1\}$ with $p\in\Bbb N$ is a semi-algebraic set, and its polar dual is
$$(*)\quad \{x\in\Bbb R^n\mid |x_1|^q+\cdots +|x_n|^q=1\},$$
...
- 13.6k
0
votes
1
answer
82
views
Combining Dantzig-Wolfe and Benders decomposition
I'm now solving an LP that has a few coupling rows (as in Dantzig-Wolfe decomposition) and a few coupling columns (as in Benders decomposition) simultaneously; other rows and columns are block-angular....
- 3
0
votes
1
answer
104
views
Do subgradient inequalities hold for matrix convex functions?
Suppose $f$ is a matrix convex function over symmetric, positive semidefinite matrices with spectra in some interval $I$ [1]. That is, for $A,B\succeq 0$ with spectra in $I$, and any $\theta\in[0,1]$,
...
- 253
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
1
vote
0
answers
121
views
John and Lowner ellipsoid
I am looking at a proof to show that Lowner ellipsoids are unique for centrally symmetric convex body $K$. I want to show basically that
$$
\DeclareMathOperator{\Vol}{Vol}\DeclareMathOperator{\Low}{...
- 11
2
votes
0
answers
54
views
Removing convex sets that are unions of other convex sets from a large combinatorial enumeration
An addition chain for $n$ is a sequence of integers $1=a_0<a_1<...<a_r=n$ with $a_i=a_j+a_k,i>j\ge k\ge 0$. We say $r$ is the addition chain length. We define the length of the smallest ...
- 97
2
votes
0
answers
72
views
Hidden vector recovery problem?
A certain problem has shown up in my research recently that feels like it could be a preexisting problem in convex geometry, but I am not familiar with the area.
I'll describe the problem (and a ...
- 2,183
7
votes
1
answer
184
views
In a set of n points on $R^d$, each point can be "well separated" from the rest by a linear functional. Is the dimension necessarily $\Omega(n)$?
For $x\in\mathbb{R}^d$ and $A\subset\mathbb{R}^d$, we say that $x$ is well separated from $A$ if there is a linear functional $f:\mathbb{R}^d\rightarrow\mathbb{R}$ such that $f(A)\subseteq [0,1]$ and $...
- 71
1
vote
0
answers
162
views
Convex matrix combination
We all know the notion of a convex combination like
$$\lambda x_1 \; + \; (1 - \lambda) x_2$$ for some $\lambda \in (0, 1)$.
However, I am trying to find literature where this concept has been ...
- 61
1
vote
0
answers
195
views
The image of zero-measure set under normal mapping is Lebesgue measurable
Let $u$ be a convex function defined on a bounded open set $\Omega$ in $\mathbb{R}^n$. Then $u$ is twice differentiable a.e. Let $E_u$ be the set on which $u$ is not twice differentiable. Then $E_u$ ...
- 11
4
votes
0
answers
222
views
Characterization of curves contained in the boundary of convex bodies
Given a continuous closed curve $\gamma$ in $\mathbb R^n$ does there exist a convex body $K$ (convex set with non-empty interior) such that $\gamma\subset \partial K$?
I am looking for a reference to ...
0
votes
1
answer
36
views
Benefit of adding a trivial constraint to ILPs
let ILP be an integer linear program with constraints-matrix $\boldsymbol{\mathrm{M}}\in\mathbb{Z}^{m\times n}$ and cost vector $\boldsymbol{\mathrm{c}}\in\mathbb{Z}^n$,
${\boldsymbol{\mathrm{x}}^*}\...
- 13.2k
3
votes
0
answers
280
views
Improvements to Minkowski's second theorem
Let $L$ be a (full rank) lattice in $\mathbb{R}^t$ and let $K$ be a convex body. Minkowski's second theorem states that
$$
\frac{2^t}{t!} \det(L) \leq \lambda_1 \cdot \ldots \cdot \lambda_t \text{Vol}(...
- 502
1
vote
1
answer
176
views
Tight upper-bounds for the Gaussian width of intersection of intersection of hyper-ellipsoid and unit-ball
Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $...
- 6,853
0
votes
0
answers
94
views
Boolean operation on n dimensional polyhedron
A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$.
Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
- 21
0
votes
1
answer
93
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
12
votes
3
answers
538
views
Center of convex figure
Let us denote by $|F-G|_H$ the Hausdorff distance between compact sets $F$ and $G$ in the plane.
Is it possible to choose a point $p_F\in F$ in any non-empty compact convex figure $F\subset\mathbb{R}^...
- 45k
1
vote
0
answers
85
views
More on triangles inscribed in convex regions with one vertex fixed
We add a bit to On maximum perimeter triangles inscribed in convex regions with one vertex fixed. Let C be a convex planar region and P a point on its boundary.
Are there convex shapes C other than (...
- 5,979
0
votes
1
answer
110
views
Orthogonal projection of a point centrally-symmetric closed convex subset of $\mathbb R^n$ never expands the coordinates of the point
Let $C$ be a closed convex subset of $\mathbb R^n$ which is symmetric about the standard coordinate axes. For example, think of $C$ as the unit-ball for an $\ell_p$-norm, for some $p \in [1,\infty]$. ...
- 6,853
1
vote
0
answers
88
views
If all the chocolate is within distance r of the outer boundary of the choco egg, what is the max.quantity of chocolate contained within a unit ball?
We have proved the following statement, but wonder if this result is actually known (reference??)
It solves the following problem. Suppose you have a (possibly) hollow chocolate egg whose outer ...
- 258
3
votes
0
answers
70
views
Characterizing image of integral transform applied to sections of a fiber bundle
Geometry is not my area, and so, I am not sure the title accurately captures what I am interested in exactly... I hope the tags are appropriate.
For any vector $v$, denote it's $i$-th component by $v_{...
- 181
6
votes
2
answers
341
views
For most directions does the supporting hyperplane meeting a bounded convex set meet it in one point?
Let $C\subseteq \mathbb R^n$ be non-empty, convex and compact. For $v\in S^{n-1}$, let $H_v$ be the supporting hyperplane in the direction of $v$ (i.e., $H_v$ is the boundary of the smallest closed ...
- 2,555
2
votes
1
answer
119
views
Analytic value of $\alpha := \sup_{(x,y) \in C} ax+by$, where $C := \{(x,y) \in \mathbb R^2 \mid x^2 + y^2 \le 1,\,x^2 + c y^2 \le R^2\}$
Let $a,b \in \mathbb R$, $R \ge 0$, and $c > 0$. Define $C := \{(x,y) \in \mathbb R^2 \mid x^2 + y^2 \le 1,\,x^2 + c y^2 \le R^2\}$, and set
$$
\alpha := \sup_{(x,y) \in C} ax + b y.
$$
Question. ...
- 6,853
4
votes
1
answer
303
views
On maximum perimeter triangles inscribed in convex regions with one vertex fixed
Ref: Convex curves with many inscribed triangles maximizing perimeter
Given a planar convex region C. Let P be a variable point on its boundary.
Observations: When C is an ellipse, the variation in ...
- 5,979
0
votes
1
answer
67
views
Analytic formula for minimizer of $f(x) := \sqrt{(x-a)^\top S(x-a)}+ r \|x\|_2$
Let $S$ be a positive-definite $n \times n$ matrix and define $\|z\|_S := \sqrt{x^\top S x}$ for any $x \in \mathbb R^n$. Let $a$ be a fixed vector in $\mathbb R^n$ and $r \ge 0$, and consider the ...
- 6,853
0
votes
1
answer
538
views
Method for (binary) optimization under constraints
I would like to know if there is a method to solve the Problem.
Problem:
Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \...
- 3
0
votes
1
answer
99
views
When a polygonal line become a loop in hyperbolic plane?
Suppose we have a 5 tuple of positive real numbers $(l_1,l_2,m_1,m_2,m_3)$, with $m_i \in (0,\pi)$ for all $i$. Now fix a point $v_1$ in the hyperbolic plane. Then consider a geodesic of length $l_1$ ...
- 613
4
votes
1
answer
106
views
Mean width of a simplex as one edge becomes longer
Consider an edge $e$ of a simplex $C$. If we increase the length of $e$ while keeping the length of other edges constant, the width of $C$ increases in some directions and decreases in other ...
- 1,608
2
votes
0
answers
36
views
Matrix affine functions and matrix convex sets
In this post I'm trying to understand a small but significant part of an article by Corran Webster and Soren Winkler regarding a matrix convex generalization of the Krein-Milman theorem. (see the ...
- 21
0
votes
0
answers
139
views
Anti-concentration of the $\ell_2$ norm of log-concave measures
This question is regarding a special case of this question, for which it is plausible the details are known.
The Carbery-Wright inequality is an "anti-concentration inequality" that states ...
- 2,183
1
vote
0
answers
59
views
How do I incorporate Ito's lemma into the solution for a finite-horizon stochastic cake-eating problem?
I'm interested in finite-horizon, continuous-time cake-eating problems in which the agent has a time-horizon $W$ over which to eat the cake, and then chooses an optimal consumption path $\{h_t\}_0^W$, ...
- 11