Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [convex-geometry]

Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.

0
votes
0answers
23 views

Is there any kind of trigonometry analog for solids?

I'm looking for a general method of calculating angles in convex tetrahedra, a 3-dimensional analog of trigonometry. Have someone established such system in a formal way?
3
votes
1answer
34 views

How to approximate a 3x3 linear inequality constraint

Let $M$ be a $3\times3$ symmetric matrix (6 independent variables). The following constraint: $$M \succeq 0$$ is a convex linear matrix inequality (LMI), meaning that M is positive semidefinite. I'...
0
votes
0answers
15 views

Strongly convex with respect to norm of Ellipsoid

In $\mathbb R^n$ with Euclidean norm $\|\cdot\|$, a convex set $\Omega$ is set to be strongly convex with respect to the norm $\|\cdot\|$ if there exists $\alpha>0$ such that for any $x,y\in \Omega$...
0
votes
0answers
27 views

the sum of many polytopes has round shape.?

I generate 1000 polytopes $P_1, \ldots, P_{1000}$ in $\mathbb R^{n}$, each of them has $m$ vertices that are $m$ rows of an $m\times n$ matrix $A_i={\sf rand(m,n)}$. Then I take their sum $P=P_1+\...
0
votes
0answers
37 views

Show that a ball is contained in at least one overlapping convex set

Consider a convex domain $\Omega\subset\mathbb R^n$ and a collection of convex sets $A_i\in\Omega$, $i=1,2,...,N$, whose union contains $\Omega$. Define the $i$-th overlap $\kappa_i$ as the largest ...
0
votes
0answers
8 views

Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra

Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$) (Equivalently, $\Delta$ is the convex hull of $\{(0,...
0
votes
0answers
22 views

Properties of Splitting Convex Sets

Say I have a convex set of $n$ dimensional polynomials that satisfy certain properties $P$. I then want to split $P$ into two disjoint sets $P_U, P_S$ such that $P_S\cup P_U = P$ and $P_S \cap P_U = ...
1
vote
1answer
28 views

Alternating Projection Convergence Proof

Following the Convergence proof (on page 3) from Alternative Projection paper: https://web.stanford.edu/class/ee392o/alt_proj.pdf I know intuitively how to show that both sequences {$ \left\lVert y_k ...
1
vote
0answers
37 views

Prove that a cone is convex if and only if it is closed under addition.

Let $K \subset \mathbb{R}^n$ be a cone. A cone is defined as: $(\forall x\in K) \wedge (\forall \lambda>0) \Longrightarrow \lambda x\in K$. Prove that: $K$ is convex $\Longleftrightarrow K$ is ...
0
votes
1answer
30 views

Boundedness of sublevelsets of strongly convex functions implies boundedness of second-order gradient

In page 460 of Stephen Boyd's "Convex Optimization", he described a property of strongly convex functions: "The inequality (9.8) (i.e. $f(y) \geq f(x) + \nabla f(x)^T (y - x) + \frac{m}{2} \|y - x\|...
2
votes
1answer
143 views
+100

Stable strict local minimum implies local convexity

Let $\bar{x}\in\mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a $C^2$ function. We have known that if $\nabla f(\bar{x})=0$ and $\nabla^2f(\bar{x})>0$, i.e. $\nabla^2f(\bar{x})$ is ...
3
votes
4answers
483 views

how to draw the space of such linear combinations?

We have the linear combination $$ {2 \choose 1 } x_1 + {1 \choose 2} x_2 + {1 \choose -2} x_3 + {1 \choose 1} x_4 + {-1 \choose 0 } x_5 + {0 \choose -1 }x_6 $$ As $x_i \geq 0 $ is given, according ...
0
votes
0answers
42 views

a compact set with nonempty convex sections

Let $X = [0,1]^d$ be the unit cube in the $d$-dimensional Euclidean space. For every $x \in X$ and every coordinate $i=1,2,\ldots,d$ denote by $x_{-i} := (x_j)_{j \neq i}$. Given a set $Y \subseteq X$ ...
1
vote
2answers
25 views

Using Alternative Projection Algorithm to solve linear systems

We can find $x^*$ which converges to the intersection point of convex sets using Alternative projection algorithm. A linear system $$Ax=b$$ can be considered as a set of hyperplanes $H_i := \{x \in ...
0
votes
2answers
29 views

Writing the equation of hyperplane separates a point and a convex set

Consider a point, $v$ outside a closed convex set $C$ and $\omega \in C$. Let $v^*$ be the orthogonol projection of $v$ onto $C$. Can I write the equation of the hyperplane goes through the projection ...
0
votes
1answer
33 views

Orthogonal projection of a vector onto convex set

What is the meaning of an orthogonal projection of a vector onto a convex set? I am familiar with orthogonal projection of a vector onto a vector space but I cannot ...
0
votes
2answers
56 views

Counterexample: Convex set which is NOT the intersection of half-spaces

half-space: either an open half-space, a closed half-space, or a set $H$ s.t. $$ H^{o} \subsetneq H \subsetneq \bar{H} \,,$$ where the relative interior $H^o$ is an open half-space and the relative ...
0
votes
1answer
23 views

Distance between the boundaries of a convex set and its shrunk version

Let $S$ be a compact convex set and $S'=\{x\in S: d(x, \partial S)\ge \delta\}$, where $d$ is the Euclidean distance and $\partial S$ is the boundary of $S$. Assume that we choose $\delta>0$ such ...
0
votes
0answers
7 views

Ratio volume convex body and smallest box containing that body

Let $V\subset \mathbb R^d$ be a convex compact set of positive volume. Write $C$ for the unit cube. Does there exist an $r>0$, depending only on $d$ and not on $V$, such that there exists an affine ...
0
votes
1answer
39 views

An Impossibility Theorem in $\mathbb{R}^3$

It's a trivial though verbose to note, that in $\mathbb{R}^2$ if you have a point $p$ contained between parallel lines $l_1, l_2$ and if $p$ is formed by the intersection of 2 rays $r_1, r_2$ (...
2
votes
0answers
84 views

Understanding whether a set of vectors is convex

I have a set $\Theta$ of vectors $\theta$ and I want to find whether $\Theta$ is convex. The difficulty that I have is related to some "peculiar" constraints that I impose on some components of $\...
1
vote
2answers
26 views

Algorithm for Finding a Conic Combination Giving the Zero Vector

Suppose I have a set of vectors $\{\mathbf s_1, \dots, \mathbf s_N\} \subset \mathbb Z^n$, and I want to find all conic combinations that give the zero vector. In other words, I want to find all ...
1
vote
1answer
21 views

How to conclude $ \left\lVert x_k - \bar x \right\rVert_2 \le \left\lVert x_0 - \bar x \right\rVert_2$

There are 2 intersecting convex sets and I am discussing about alternating algorithm related to those convex sets. I obtain the following results $ \left\lVert y_k - \bar x \right\rVert_2^2 \le \...
2
votes
0answers
40 views

The set of vectors whose coordinates are non-negative and sum to a number less than $1$

Let $n \in \{1,2,\dots\}$. Consider the convex set consisting of all $(x_1,\dots,x_n) \in \mathbb{R}^n$ satisfying: $x_i \geq 0$, $i \in \{1,\dots,n\}$ $x_1 + \cdots + x_n \leq 1$ Does this set ...
3
votes
0answers
44 views

What is known about these “transparent” polytopes?

I am looking for the name (if there is one), simple properties and possible literature for the following class of polytopes (by polytope I mean the convex hull of finitely man points in $\Bbb R^n,n\ge ...
1
vote
0answers
17 views

Valuation Property for mean width

For some polyhedron, $P$, define the mean width function, $$H(P)=\sum_{e\in E} L_e(\pi - \delta_e)/(4\pi)$$ Where $E$ is the set of all edges of the polyhedron, $L_e$ is the length of edge $e$ and $\...
0
votes
0answers
15 views

The dual of a regular polyhedral cone is regular

A rational polyhedral cone in $\mathbb{R}^n$ is a set of the form $$\sigma=\{\lambda_1x_1+\dots+\lambda_kx_k\in \mathbb{R}^n\mid \lambda_i\in \mathbb{R}_{\geq 0} \; \;\forall \, 1\leq i\leq k\}$$ for ...
3
votes
1answer
54 views

Estimate the volume of Voronoi cell

Let given a ball of radius $\alpha$ centered in point $u$ in $d$-dimensional space. Let given a sample of $n$ uniformly distributed vectors $x_i$ ($i = 1,\dots,n$) inside the ball. For each vector $...
0
votes
1answer
22 views

Interpreting strong convexity geometrically

According to the definition, function $f$ is strongly convex if and only if for all $x$ and $y$ where $t>0$, $$ f(x) \geq f(y) + \langle\nabla f(y), x-y\rangle + \frac{\gamma}{2}\Vert x-y\Vert^...
0
votes
0answers
34 views

Convex Hulls and maximizing volume

I thought of a function (recreational mathematics) and wonder if there is any existing math about it. Google searching did not turn anything up. Let $n\in \mathbb{N}$ be the dimension, and $x\in \...
1
vote
1answer
29 views

Polytope in Minkowski sum

Is the following statement true? Suppose that $P$ is a polytope contained in the Minkowski sum $A+B:=\{a+b: a\in A, b\in B\}$ of two convex compact sets $A$ and $B$. Then there exist polytopes $Q\...
0
votes
0answers
31 views

Minimal/Small convex partition of a set of points

Given a set of $n$ point tuples $(x_1, y_1), \ldots, (x_n, y_n)$ with $x_i, y_i \in \mathbb{R}^m$. I am interested in a partition of a hypercube the points $x_1, \ldots, x_n, y_1, \ldots, y_n$ are ...
0
votes
1answer
62 views

Lower bound for the number of edges in a Minkowski sum

I was wondering whether the following statement about a Minkowski sum of two polytopes is true: Let $P=P_1 + P_2$ be the Minkowski sum of two polytopes $P_1$ and $P_2$ in $\Bbb R^n$, i.e. $P=\{p_1+...
1
vote
1answer
32 views

Why recession cone of a set $C$ is indeed a cone?

The recession cone of a set $C$, i.e., $R_C$ is defined as the set of all vectors $y$ such that for each $x \in C$, $x-ty \in C$ for all $t\geq 0$. On the other hand, a set $S$ is called a cone, if ...
0
votes
1answer
28 views

Does the following set of polynomials non-negative on the interval $[0,1]^2$ positively span all non-negative polynomials on the interval?

Given the following set of polynomials that are non-negative on the interval $[0,1]^2$ $$ B = \{x, 1-x, y,1-y,xy,x-xy,y-xy,1-x-y+xy\} = \{b_1,b_2,...,b_8\} $$ Can we definitively say that all ...
2
votes
1answer
124 views

Convex side of a spherical mirror

A convex set has the property that if you take any two points in the set and draw the line segment connecting those two points, that line segment lies entirely in the set. My textbook says that ...
0
votes
1answer
36 views

About theory of convex cones

Working with positive semidefinite matrices I discovered the concept of convex cone. That is, a subset $C$ of a vector space $V$ that is closed under positive linear combinations. I had never read ...
1
vote
0answers
29 views

Is the dual of a cone can be defined by the dual of the closure of its convex hull?

Let $K$ be a nonempty cone in $\mathbb{R}^n$. We denote the dual of a cone $K$ as $K^*$. Show that $$K^*=(\mathop{\boldsymbol{cl}} \mathop{\boldsymbol{conv}}K)^*$$ How can we describe the closure of ...
1
vote
0answers
22 views

Intuition of convex set separation hyper-plane

According to the hyperplane separation theorem Let A and B be two disjoint nonempty convex subsets of Rn. Then there exists a non-zero vector v and a real number c such that $$ <x,v> \le c $$ ...
1
vote
0answers
16 views

Is the volume of the largest hyperrectangle inscribed in a convex polytope always larger than some fixed proportion of the polytopes volume?

Fix a positive integer $n$. For any convex polytope $\mathcal{P}$ of dimension $n$, let $V_\mathcal{P}$ denote its volume and let $K_{\mathcal{P}}$ denote the maximum possible volume of an $n$-...
0
votes
1answer
33 views

Does there exist a basis of a Convex Cone

We are given a set $C \subset V$, where $V$ is a vector space. $C$ is a convex cone, so it has the following properties $$ 0 \in C $$ $$ C+C \in C $$ $$ x\cdot C\in C\mid x\in\mathbb{R} \land x\...
0
votes
0answers
22 views

Lower-bounding Gaussian inner products with high probability

Suppose that $K\subseteq \mathbb R^n$ is a proper convex set with piecewise smooth boundary and that $0 \in K$. Assume that $x \in K$ and let $z \sim \mathcal{N}(0, I_n)$ be a Gaussian random vector. ...
3
votes
0answers
47 views

An inequality relation of convex decreasing function

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be convex decreasing function. I read from somewhere that we have the following inequality: For any $x\leq y$ and $t\geq 0$, $f(x+t) - f(x) \leq f(y +t) -f(...
3
votes
1answer
28 views

Separation of subsets of $\mathbb{R}^n$ with the graph of a convex function

Let $A, B \subset \mathbb{R}^n$ be compact and disjoint sets. Assume that there exists a $(n-1)$-dimensional surface $S$ such that separates the $A$ and $B$, i.e. there exists $C \subset \mathbb{R}^n$...
0
votes
0answers
31 views

Analogue of subcontractive property of Hilbert space projections for general Banach spaces

Let $ X $ be a Banach space over the reals with norm $ \| \cdot \| $. Let $ C $ be a nonempty closed convex subset of $ X $. Suppose $ a \notin C $. Is it true that there exists $ b \in C $ such that $...
4
votes
1answer
36 views

Convexity of a convex set minus points close to its frontier.

Let $d\geq 1$. Let $K\subset\Bbb{R}^d$ be a convex set, $\varepsilon>0$, and $K(\varepsilon)\subset K$ the points of $K$ whose distance to $\partial K$ is less than $\varepsilon$. Is $K\setminus K(...
0
votes
0answers
7 views

What separates a cyclic polytope from a projective polytope?

I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries. The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
0
votes
1answer
21 views

Inexistence of norm in $\mathbb{R}^2$

Prove that there is no norm in $\mathbb{R}^2$ such that the balls are six-pointed stars. I'm aware this has to do with connexity, but not sure how to procced... If the star has empty interior then it'...
0
votes
0answers
49 views

Area calculation in a convex quadrilateral

I´ve some problem with the area calculation in a convex quadrilateral. My problem looks like this: Let $ABCD$ be a convex quadrilateral with points $X$ and $Y$ on side $AB$ so that $AX = XY = YB$, ...
2
votes
1answer
44 views

Convex hull of set of points inside a half-space

We place ourselves in $\Bbb{R}^d$, for $d\geq 1$. Let $\mathcal{h}$ a hyperplane, and let $S$ be a finite set of points that all lie in one of the (closed) half-spaces limited by $h$. Let $C$ denote ...