A branch of geometry dealing with convex sets and functions. Polytopes, convex bodies, discrete geometry, linear programming, antimatroids, ...

learn more… | top users | synonyms

0
votes
0answers
71 views

Differntiability of Distance to a CLosed Convex Set

Let $A$ be a closed convex set in Banach space $( \mathbb{R}^n, \| \cdot\| )$. For any $\mathbf{x} \in \mathbb{R}^n$, define $$P_{A}(\mathbf{x}) = \arg\min_{\mathbf{y}\in A} \| \mathbf{x} - \mathbf{y} ...
0
votes
0answers
76 views

Looking for an exposition of a certain theorem of Talagrand

The following is a theorem by Talagrand (as stated here, http://arxiv.org/pdf/1511.08609v1.pdf), Let $(X, \mu)$ be a probability space. Let $F : X \rightarrow \{0,1\}$ be a family of functions ...
5
votes
1answer
143 views

Structure of a real 3x3 positive-semidefinite matrix whose eigenvalues verify the triangle inequalities

It is known that a 3 by 3 real symmetric matrix $A$ has an eigendecomposition $$ A = Q E Q^T $$ where $Q$ is an orthogonal matrix and $E$ is a diagonal matrix whose elements, $E_{11}$, $E_{22}$ and $...
1
vote
0answers
33 views

Compute Mixed Volume with Respect to Some Regular Sets

Let $( \mathbb{R}^n, \mathcal{B}, \gamma)$ be a measure space where $\mathcal{B}$ is the Borel sigma algebra and $\gamma$ is a continuous measure. For $A, B\in \mathcal{B}$ that are convex, the mixed ...
2
votes
1answer
347 views

Can the Units of a Cubic Field be Proven from Pigeonhole Principle alone?

I would like to run through the proof of Dirichlet Unit Theorem for a cubic field. Let's try $\mathbb{Q}[x]/(x^3 - x - 1)$. This has 1 real root and 2 complex roots (or embeddings). The units in ...
0
votes
0answers
40 views

Equivalent Definitions of the Gaussian Surface Measure for Regular Sets

I wonder if the following definitions of the Gaussian surface measure are equivalent. First, let $\mathbb{R}^n$ be the Euclidean space and $A \subseteq \mathbb{R}^n$ be a sufficiently regular set, e....
0
votes
0answers
28 views

Approximating Minkowski Sum of 3 dimensional Convex Polytopes by Sampling

Let $P_1,P_2...P_r$ be a set of convex polytopes with $n_r$ vertices in 3 dimensions. These polytopes basically represent uncertainties of '$r$' number of 3d-points respectively in space. The global ...
1
vote
1answer
53 views

Enclosing a convex plane domain in a disc

The following statement seems obvious to me: Let $\gamma:S^1\to\mathbb R^2$ be a smooth injection such that $\dot\gamma$ and $\ddot\gamma$ never vanish. Then $\gamma$ encloses a strictly convex ...
1
vote
1answer
147 views

Integral points - monotone symplectic toric manifolds

Suppose I am given a symplectic toric manifold $(M,\omega,\psi)$ which is also monotone, hence the symplectic form can be rescaled so that $c_1=[\omega]$. Then the moment map can be taken so that its ...
1
vote
0answers
58 views

On convex hull of algebraic curve

For any given tuple of quadratic functions $(f_1(x,y,z),f_2(x,y,z),f_3(x,y,z))$, the following set forms a algebraic curves $$ S_{f_1,f_2,f_3}=\{(f_1(x,y,z),f_2(x,y,z),f_3(x,y,z))|x^2+y^2+z^2=1,x,y,z\...
0
votes
0answers
40 views

Limit of argmin of sum

Suppose that I know $f_n\rightarrow f$ and $g_n\rightarrow g$ are both continuous maps from a Complete Riemmanian Manifold $X$ to $\mathbb{R}$ which converge pointwise almost everywhere. Then is it ...
4
votes
1answer
77 views

Extremal Lipschitz convex functions

Let $B_d$ the unit ball in $\mathbb{R}^d$, and let $F_d$ be the set of convex functions with Lipschitz constant at most 1 from $B_d$ to $\mathbb{R}$. When $d=1$ (so the domain is the just the ...
5
votes
1answer
127 views

Decidability of convex rearrangements of polygons

Triggered by the MO question, "How many convex shapes can be made with the pieces of the Stomachion?," I would like to pose this question: Q. Given $n$ polygons in a set $S$, say each with integer ...
1
vote
0answers
60 views

A third degree surface and a touching sphere [closed]

Let consider a surface $z=1/(xy)$ and a sphere defined by $(x-1.5)^2+(y-1.5)^2+(z-1.5)^2=3/4$. The sphere touches the surface at (1,1,1). Is it possible to prove that point (1,1,1) is the only ...
8
votes
0answers
117 views

Tensor Product of Convex Sets?

I was wondering if such a concept was used anywhere. What I was thinking of is this. Consider two vectors spaces $V,W$ and convex sets $C_1 \subseteq V$ and $C_2 \subseteq W$ if we define $C_1 \otimes ...
3
votes
0answers
64 views

Algorithm to calculate moments of uniform distribution on convex polyhedra

There is system of linear inequalities $$ Ax \leq K, $$ $$ x\geq a, x\leq b. $$ $A$ is $(n\times m)$-matrix, where $n\approx 100$ and $m\approx 10000$, $rank(A)=n$. Suppose that on set of solutions ...
8
votes
1answer
150 views

Convex body with affine-equivalent cross-sections

I recently discovered the following fact: Let $K\subset\mathbb R^3$ be an origin-symmetric convex body with smooth and strictly convex boundary. Suppose that all central cross-sections of $K$ (that is,...
8
votes
3answers
271 views

Shape whose translated and scaled copies are closed under intersection

The translated and scaled copies of an equilateral triangle with fixed orientation are closed under intersection - the intersection is again an equilateral triangle with the same orientation. What ...
7
votes
1answer
202 views

Partitioning a convex object without harming existing convex subsets

$C$ is a convex planar figure and $C_1,\dots,C_n$ are pairwise-disjoint convex subsets of $C$, like this: A convex-preserving partition of $C$ is a partition $C=E_1\cup\dots\cup E_N$, , such that $...
2
votes
1answer
93 views

Lipschitz constant of cental projection of unit ball to surface of convex body

Let $X$ be a real normed space equipped with $\lVert\cdot\rVert$ and $M$ be a convex set in $X$, such that $B(0,r) \subset M \subset B(0,R)$ for $r>0$. Here $B(a, t)$ stands for closed ball with ...
1
vote
1answer
66 views

Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces

Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by $$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$ $$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$ I wish to find their convex hull, that is a ...
1
vote
0answers
26 views

Least Width of Planar Unimodal Curves with Unit Diameter

I am currently trying to find a way to define some notion of "roundness" for subtours in graphs and that definition should only be based on the comparing (sums of) edge length and on the order in ...
1
vote
0answers
28 views

Is support function of a convex curve in $\mathbb{R}^2$ absolutely continuous? [closed]

There is an example of a convex function of two variables that is convex but not absolutely continuous. The level set of this function is a convex curve. To construct one example of such a function ...
5
votes
1answer
148 views

Upper bound on the number of convex connected components of the complement of the zero set of a polynomial

The classic Milnor-Thom upper bound on the sum of the Betti numbers of real algebraic sets (for a nice exposition and references, see e.g. N.R. Wallach, On a Theorem of Milnor and Thom, in S. Gindikin ...
6
votes
2answers
299 views

Atiyah-Guillemin-Sternberg convexity theorem

I would like to study the Atiyah-Guillemin-Sternberg convexity theorem: proof and applications. I am already familiarised with hamiltonian actions, moment maps...and with elementary Morse theory. So ...
3
votes
1answer
165 views

A lottery on coins in a convex set

You play the following game. You get $4n$ gold coins and have to arrange them in the unit square in general position (no two coins have the same x or the same y coordinate). Call this set of coins $...
4
votes
3answers
139 views

Cluster Variables for non-convex n-gons

Most of the lectures and lecture notes on Cluster Algebras (at least from Combinatorial point of view) start with mutations of the diagonals of a convex n-gon (mostly the pentagon) as the illustration ...
3
votes
1answer
128 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\ $ ...
15
votes
1answer
662 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<\...
1
vote
0answers
73 views

Projecting on a a special polyhedron

Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron $$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$ Notice that $\mathcal P_X$ is symmetric about the origin. ...
1
vote
0answers
45 views

Projecting on a convex compact polytope with special form

Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
2
votes
4answers
135 views

Show that the Minkowski sum of two triangles in 3D is the union of Minkowski sums of each triangle along the other's edges?

I'd like to show (or disprove) the claim that the Minkowski sum of two triangles with vertices in $\mathbb{R}^3$, $A+B$, is equal to the union of the unions of the Minkowski sums of $A$ along all ...
1
vote
0answers
37 views

Checking integer points of given infinity norm on intersection

If we have convex region $\mathscr R$ given as intersection of a convex polytope $\mathscr P$ and an ellisoid $\mathscr E$ in $\ell^2$ norm is there an efficient way to test if there is an integer ...
2
votes
2answers
51 views

Can we prove that a normal surface of an extreme point of a convex subset of a simplex is a separating hyperplane?

Let's assume that we have a simplex $G = \{x\in R^d|\sum_{i=1}^d x_i=1, x_i\ge 0 , i = 1, 2, .., d\}$ and a polyhedral convex subset $H \subseteq G$. Is it possible to prove that for any extremal ...
14
votes
1answer
377 views

Minimize sum of $\ell_2$ norm and linear combination, on simplex

Let $\Delta_n := \{x \in \mathbb{R}^n | x \ge 0, \sum_{1 \le i \le n}x_i = 1\}$ be the $n$-simplex. For $a, b \in \mathbb R^n$, with $\Delta_n \not \ni a$, consider the problem of computing the ...
6
votes
0answers
58 views

Convex hull of the orbit of a matrix under permutations

Let $P$ be a generic permutation matrix on $\mathbb{R}^n$. For any vector $x \in \mathbb{R}^n$, the convex hull of the set $\{ Px : \; \text{$P$ is a permutation matrix}\}$ is the set of vectors ...
4
votes
1answer
202 views

Questions about the regularity of the “norm” associated to a convex set

Suppose $K\subset \mathbb{R} ^n$ is a closed convex set whose interior contains the origin. We can assign a gauge function to $K$ as $g_{K}(x):=\inf\{\lambda>0 \mid x\in\lambda K\}$. $g_K$ has all ...
5
votes
0answers
77 views

What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?

Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
0
votes
0answers
26 views

Efficient sampling from a polytope with large number of contraints [duplicate]

As far as I know, the most popular way to sample from a polytope (in H-representation) \begin{equation} \mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\} \end{equation} ...
1
vote
0answers
46 views

Number of simplices contained in a convex body

I am interested in the following question: Given a convex body $K$ in $\mathbb{R}^d$ and an $\epsilon>0$ small enough, how many $d$-simplices $\{D_i\}_{i=1}^m\subset K$ do we need at least so that ...
0
votes
0answers
65 views

Maximum value of linear function on the intersection of a parametrized family of balls

Let $C$ be a (nonempty) closed convex subset of $\mathbb{R}^n$ and $a, b \in \mathbb{R}^n$. Using the normal cone characterization of the euclidean projection operator $\mathrm{proj}_C$ (recall that $\...
14
votes
0answers
280 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 \...
2
votes
1answer
77 views

Internal edges in Convex Polytopes

Suppose $S\subset{\mathbb R}^n$ is an infinite subset that is in general position which means that the intersection of $S$ with every affine subspace of dimension $d<n$ always contains at most $(d+...
3
votes
1answer
125 views

How to show it is contained in a convex hull?

There are $(d+1)f$ points (denote the set of all points as $S$) in $\mathbb{R}^d$, that can be divide into $d+1$ disjoint sets $F_1,...,F_{d+1}$, each set of size $f$. If we have $$ \mathcal{H}(F_i)\...
4
votes
0answers
113 views

Alexandrov-Fenchel inequality for sets of positive reach

If $E$ is a convex subset of $\mathbb{R}^n$ with $|E| = |B_1|$, then one consequence of the classical Alexandrov-Fenchel inequalities from convex geometry is that $$\int_{\partial E} H_{\partial E} \,...
1
vote
0answers
71 views

Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb R^2$...
0
votes
1answer
134 views

Convex cones: strict separation

Consider two closed convex cones $A$ and $B$ in $\mathbb{R}^3$. Assume that they are convex even without zero vector, i.e. $A \setminus \{0\}$ and $B \setminus \{0\}$ are also convex (it helps to ...
4
votes
0answers
188 views

Osculating ellipsoids

Let $K$ be a given smooth, origin-symmetric, strictly convex body in $n$ dimensional euclidean space. At every point $x$ on the boundary of $K$ there exists an origin-symmetric ellipsoid $E_x$ that ...
5
votes
1answer
188 views

Ascertain properties of a new kind of rectilinear-convex set

PREABMLE TO MY QUESTION I am reading about convex sets and hulls in orthogonal/rectilinear spaces. As can be seen in this publication, for a given set of points in $\mathbb{R}^{2}$, there are many ...
3
votes
1answer
137 views

A family of convex bodies in Banach-Mazur position

Let $\{K_i\}$ be a family of smooth, origin-symmetric, strictly convex bodies such that $K_i$ converge in the Hausdorff distance (or you may assume $\partial K_i\to \partial K$ smoothly, in the sense ...