**2**

votes

**0**answers

63 views

### Optimization over a variable domain defined as a convex hull of given points [closed]

I have an optimization problem:
$\max_{\bf{x}} Z(\bf{x})$,
s.t. $\bf{x} \in conv(\bf{S})$
where $\bf{x}$ is an $n$-dimensional vector, $Z(\bf{x})$ is a non-linear function. The domain of $\bf{x}$ ...

**6**

votes

**2**answers

212 views

### Volumes of convex vs non-convex polyhedra with prescribed facets areas

It is known that given a set of Areas $A_f$ and normals $\vec{n}_f$ if $\sum_f A_f \vec{n}_f=0$ exist a unique convex polyhedron with given face areas and normals. (Minkowski theorem - See Alexandrov ...

**1**

vote

**3**answers

169 views

### How to determine if two rational cones intersect?

Let $$\displaystyle C_1=C(r_1,...,r_{n_1})=( x\in \mathbb{R^d}|x=\sum_{i=1}^{n_1}\lambda_i r_i, \lambda_i\in \mathbb{R_{>0}})$$
$$\displaystyle C_2=C(t_1,...,t_{n_2})=(x\in ...

**2**

votes

**1**answer

235 views

### Lattice points in cross-polytopes

Let $E\subset \mathbb{R}^n$ be a cross-polytope:
$$E= \left\lbrace x : \frac{|x_1|}{q_1}+\cdots+\frac{|x_n|}{q_n}\leq 1 \right\rbrace, $$
where $q_1,\dots,q_n$ are positive integers. I am interested ...

**7**

votes

**1**answer

161 views

### Do there exist “expanding” $1$-skeletons of simple $4$-polytopes?

Let $\{ G_n \}_{n \ge 1}$ be a sequence of graphs such that the number of vertices of $G_n$ tends to $\infty$ as $n \to \infty$. We say that $\{ G_n \}_{n \ge 1}$ is an expander family if
$\lambda_2( ...

**4**

votes

**1**answer

186 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 ...

**4**

votes

**1**answer

213 views

### convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...

**9**

votes

**1**answer

309 views

### Needle probing for a convex body

Suppose there is an unknown closed convex body $K$ of
volume vol$(K) = V$ inside the
unit cube $[-\frac{1}{2}, \frac{1}{2}]^d$ in $\mathbb{R}^d$.
You are permitted to probe with a (one-dimensional)
...

**8**

votes

**3**answers

432 views

### Rate of growth of an explicit integral

Let $$J_1=\int_0^1\frac{1}{\sqrt{1-t_2}}dt_2,$$
$$J_2=\int_0^1 \int_0^{t_2}\frac{1}{\sqrt{1-t_2}}(\frac{1}{\sqrt{1-t_3}}+\frac{1}{\sqrt{t_2-t_3}})dt_3dt_2,$$
$J_3=\int_0^1 ...

**9**

votes

**1**answer

375 views

### Question about tetrahedron decomposition

Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...

**10**

votes

**1**answer

406 views

### When is a matrix similar to a non-negative matrix?

Consider a real square matrix $A$ of size $n\times n$. Under which conditions on $A$ does there exist a row-stochastic matrix $U$ (non-negative, rowsums = 1), such that $A'=U^{-1}AU$ is a non-negative ...

**3**

votes

**1**answer

164 views

### Simplex with edges of length at least s having smallest circumradius

Is it true that of all $n$-simplices with edge lengths greater than or equal to some parameter $s$, the regular simplex with edge lengths $s$ has the smallest circumradius? It seems obvious, but I ...

**5**

votes

**2**answers

244 views

### Diameter-area ratio for affine tranformations.

Consider an convex plane figure $F$. How to prove that there is an affine transformation $a$ such that $\sqrt{3}$ diameter$(a(F))^2\leq 4$ area$(a(F))$?
I found only one reference, to "Über einige ...

**0**

votes

**2**answers

249 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 ...

**1**

vote

**1**answer

295 views

### non-convex Polytope definition

I have a simple question. I read that given a vector space $N_{\mathbb{R}}$ over $\mathbb{R}$,
we can define a convex polytope in the following way:
$$P:= \Big\{ \sum_{u\in S} \mu_u u \,\Big| \, ...

**1**

vote

**1**answer

163 views

### Straight Line Passing Through a Convex Region

Is there any test to tell me whether a straight line in a 3D euclidean space passes through a bounded closed convex region? To focus on a more specialised version of the problem, you can assume that ...

**15**

votes

**1**answer

352 views

### Does every convex polyhedron have a combinatorially isomorphic counterpart whose all faces have rational areas?

Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...

**2**

votes

**1**answer

160 views

### Does the Border (Boundary) Points of a convex body make a concave function?

Let $\mathbb{S}$ be a closed and bounded convex body in 2-D with some non-empty intersection with positive quadrant and let it also contain origin. Let $c>0$ be the right-most point on the x-axis ...

**6**

votes

**1**answer

307 views

### Does every simplicial polytope have a topology-preserving contractible edge?

An edge of a triangulated manifold is said to be contractible if it may be contracted to a vertex without modifying the topological type of the underlying manifold. Otherwise, the edge is ...

**3**

votes

**2**answers

232 views

### Formalization (and background) of a formula, concering the integral points of a polygon.

I have recently become aware of the following neat statement.
Consider a convex polygon $P$ in the real plane with integral vertices. If we associate with every integral point $(a,b)$ the monomial ...

**3**

votes

**0**answers

87 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 ...

**1**

vote

**2**answers

231 views

### Secondary Polytope Simplicial?

Is the secondary polytope of a simplicial polytope necessarily simplicial?

**1**

vote

**1**answer

116 views

### Decide inside/outside convex hull using only distances in graph

Given a weighted, undirected graph G with K knodes k1 … kK. I have a K times K matrix containing the shortest distances between each pair of points.
Is it possible (if yes how), to decide if a point ...

**7**

votes

**2**answers

1k views

### How many vertices can a convex polytope have?

One has an $n$-dimensional convex polytope $P$ represented by an intersection of half-spaces:
\begin{equation}H_i = \{ (x_1,x_2, \ldots,x_n) \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij} x_j \ge a_{i0}, ...

**5**

votes

**0**answers

212 views

### Lattice points inside a (n-dimensional) tetrahedron

Hi, overflowers.
I was interested in a sharp lower bound for the number of lattice points (say, integral lattice points) inside the tetrahedron defined by the coordinate hyperplanes and ...

**2**

votes

**0**answers

43 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 = ...

**8**

votes

**0**answers

180 views

### Does there always exist a self dual polytope that contains a given polytope contained in its dual?

Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...

**3**

votes

**3**answers

397 views

### Find a convex hull that contains given points?

Suppose that you have vectors $a_{1},...,a_{m}$ in $\mathbb{R}^n$. Can you take $n$ among them, let $v_{1},...,v_{n}$ such that $a_{1},...,a_{m}$ belong to the convex hull of ...

**1**

vote

**2**answers

134 views

### determining a convex set by mixed volumes

For a convex set $K \subset \mathbb{R}^2$ let $\phi_K:$ convexsets in $\mathbb{R}^2 \rightarrow [0,\infty), A \mapsto MV(A,K)$. Where by $MV(A,K)$ I mean the mixed volume of $A$ and $K$ in the ...

**16**

votes

**2**answers

410 views

### What is $A+A^T$ when $A$ is row-stochastic ?

This is motivated by this MO question.
If $A\in{\bf M}_n({\mathbb R})$ is row-stochastic (entrywise non-negative, and $\sum_j a_{ij}=1$ for all $i$), then $M:=A+A^T$ is
symmetric,
entrywise ...

**4**

votes

**1**answer

206 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 ...

**1**

vote

**2**answers

225 views

### Volume of intersection of a convex polytope with an affine space.

Given an $n$-dimensional polytope $P\subset \mathbb{R}^n$.
For a subset of indices $i_1,\ldots,i_k$ of $\{1,\ldots,n\}$ and reals $a_1,\ldots,a_k$, we denote by ...

**3**

votes

**1**answer

284 views

### moduli space of polytopes

When considering classification problems about polytopes, I sometimes has the feeling that one need to talk about certain parametrized families, i.e. moduli space of such polytopes. But neither do I ...

**3**

votes

**1**answer

181 views

### Classification of lattice polytopes with small number of lattice points in the facets

Suppose $P$ is a convex lattice polytope in $Z^3$ without interior lattice points, and we require the interior lattice points of each facet(i.e. dimensional 2 faces) are neither too much nor too few, ...

**2**

votes

**2**answers

394 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 ...

**1**

vote

**0**answers

166 views

### Lattice-point enumeration question involving linear combinations of matrices

I would like to know some references to learn more about an answer to this question, if there are any references:
Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, ...

**37**

votes

**0**answers

957 views

### Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let ...

**11**

votes

**0**answers

384 views

### Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices?
In other words, given any ...

**2**

votes

**2**answers

191 views

### Is there a simple test to determine whether a polytope is integral?

It is known that any rational convex polytope expressed as $\{ x\in\mathbb{R}^d : Ax \ge b \}$, where $A\in\mathbb{Z}^{k\times d}$ and $b\in\mathbb{Z}^k$, can be written as the convex hull of finitely ...

**1**

vote

**0**answers

156 views

### Compute generalized pentagram map

Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...

**8**

votes

**2**answers

364 views

### symmetries and faces of the associahedra

The dihedral group of order $2n+2$ acts on $K_n$, the $n-2$-dimensional associahedron. Are there any other symmetries? References?
Does the answer to 1 change if we restrict to just the 1-skeleton ...

**3**

votes

**3**answers

414 views

### reference for the cubical structure of the associahedra

I cannot find where I learned that the $n$-dimensional associahedron is a union of $n$-cubes. The vertices of the $n$-dimensional associahedron are the finite binary trees having $n+2$ leaves and ...

**9**

votes

**1**answer

658 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 ...

**3**

votes

**1**answer

227 views

### Empty convex polytopes for random point sets

I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane
(the Happy-Ending Problem), and I know that there are higher-dimensional extensions.
A great source ...

**4**

votes

**2**answers

305 views

### Realization spaces for regular convex polytopes

Q1.
Are there convex polytopes combinatorially equivalent to each of the regular polytopes
that are realized with integer vertex coordinates?
...

**11**

votes

**1**answer

369 views

### Can all convex polytopes be realized with vertices on surface of convex body?

The following question was asked by me on Mathematics.SE. Unfortunately, no one answered it so I thought I might give it a try one level higher. Below the line you can find the slightly edited ...

**1**

vote

**2**answers

496 views

### Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?

A corollary of Euler's formula tells us that the edge-vertex graph of every convex 3-polyhedron must have a face with either 3, 4, or 5 edges, using an argument about the average degree of vertices.
...

**19**

votes

**4**answers

633 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 ...

**1**

vote

**1**answer

361 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 ...

**0**

votes

**0**answers

105 views

### Area of spherical polygons in high dimensions

Given 4 points on $S^3$. If we look at the spherical polygon formed on $S^3$, is there a formula for the 3-dimensional Hausdorff measure for it?
E.g.: When I tried to set up a spherical coordinate ...