Questions tagged [convex-geometry]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
39 views

We have two convex sets $S,T$ such that $S\subseteq T$. Prove or disprove that the circumference of $S$ must be smaller than that of $T$. [duplicate]

This question originated from an exercise asking to compare the arclength of $y=x^2$ between $(0,0)$ and $(1,1)$ and $\frac{\pi}{2}$. The solution starts by constructing the circle with center $(0,1)$ ...
user avatar
0 votes
1 answer
44 views

What is a convex combination of graphs?

For example in this paper, they refer to a "convex combination of trees" (pg. 2, first paragraph), and also, more generally, to "convex combination of graphs" (pg. 2, footnote). -&...
user avatar
-3 votes
0 answers
19 views

Two questions about Convex Sets [closed]

There are 2 questions that I can't make any idea while solving. Can you give an idea how I can solve it? For C convex, show that C is closed if and only if C $\cap$ L is closed, for any affine line L?...
user avatar
0 votes
0 answers
38 views

Sufficient condition for convexity involving an average of slopes

Suppose $h(x)\ge0$ is increasing and concave for all $x\ge0$. For $\Delta>0$, let $$ f(x)=\frac{h(x+\Delta)-h(x)}{\Delta}. $$ I feel that $f$ is a convex function, i.e. $$ f(tx+(1-t)y)\le t f(x)+(1-...
user avatar
  • 285
2 votes
0 answers
16 views

A (sub)neighborhood $S'$ of a set $X^*$ such that the line segment connecting any point in $S'$ and its projection to $X^*$ is contained in $S'$.

Consider a closed set $X^* \subset \mathbb{R}^n$. Let $Proj_{X^*}(x)$ denote the set of metric projections of $x \in \mathbb{R}^d$ to $X^*$: $$Proj_{X^*}(x) = \arg\min_{x^* \in X^*} d(x, x^*)$$ where ...
user avatar
4 votes
0 answers
52 views

If a polyhedron's faces and vertex figures are convex, is the polyhedron convex?

Suppose a polyhedron's faces are convex polygons, and its vertex figures are convex spherical polygons (or convex cones, depending on definitions). Must the polyhedron be convex? The polyhedron may be ...
user avatar
  • 4,151
0 votes
0 answers
27 views

Is there a characterisation for the convex set which is fully embedded inside a convex polytope?

As per the Krein-Milman theorem, any convex compact set (in a finite-dimensional vector space) is equal to the convex hull of its extremal points. I am now imposing that a given convex compact set $C$ ...
user avatar
5 votes
2 answers
142 views

Minimal polytope enclosing a sphere

Given a unit ball in d dimensions (euclidean distance) and an allotment of points $n > d$, can we choose the set of n points such that their convex hull contains the ball and the volume of the ...
user avatar
  • 51
0 votes
2 answers
38 views

When the convex combinations of two vectors are all non-negative?

Let $x=(x_1,\cdots,x_N),y=(y_1,\cdots,y_N)$ be two elements of the Euclidean space $\mathbb{R}^N$. What are the necessary and sufficient conditions on $x$ and $y$ for the following statement to be ...
user avatar
1 vote
0 answers
24 views

Closed mid-point convex set and it's usefulness

$(X, \|•\|) $ be any normed space and $E\subset X$ . $(I)$ For every sequence $(x_n), (y_n) \in E$ with $x_n\to x $ and $y_n\to y $ in the space $(X,\|•\|) $ implies $\frac{x+y}{2}\in E\space \space $...
user avatar
  • 3,929
1 vote
0 answers
48 views

What's the combination of vectors with all coeffiencts between 0 to 1?

Assume a combination of the form: $\vec{S}=\sum_ip_i\vec{v}_i$ with $0\le p_i\le 1$, what is this combination called? And considering the set: $$\mathcal{S}=\{\sum_ip_i\vec{v}_i \mid 0\le p_i\le 1\}$$ ...
user avatar
2 votes
1 answer
32 views

Some doubts regarding determinant lower bound of linear discrepancy

I am reading the book on Discrepancy Theory by Matousek. A famous theorem of Lovasz et. al. implies the following lower bound on linear discrepancy of a set system. (I am attaching a screenshot of the ...
user avatar
0 votes
0 answers
16 views

Generalization of Eaves' Theorem

Let $K\subset \mathbb{R}^n$ be a nonempty convex compact and $f:K\to K$ be a function. Let $g:K\to \mathbb{R}^n$ be $g(x)=f(x)-x$. Is there always a point $x_0\in K$ such that for all neighbourhood $U\...
user avatar
  • 425
1 vote
1 answer
52 views

Maximize the trace of the convariance of a bounded random vector

Given a random variable $X$, satifying $P(0\leq X \leq 1)=1$, and $\mathsf{E}[X^2] = \alpha$. We know its maximum variance $\text{Var}(X) = \alpha(1-\alpha)$ achived by a binary random variable $P(X =...
user avatar
-5 votes
2 answers
73 views

Concavity of the function $|f|$ , while $f$ is concave [closed]

Prove or disprove, "if $f$ is concave function, then $|f|$ is also concave". I know the result is false for conves function, but for concave function, I guess it is true. But I am unable to ...
user avatar
  • 12.3k
1 vote
1 answer
42 views

Support cones and linear functionals

Let $S\subset\mathbb{R}^n$ be any set. A convex cone $C$ with apex $a$ and non-empty interior is a support cone of $S$ at $a$ if i) $a \in S,$ ii) $S \subset (\text{int} \;C)^{\complement}$ (i.e ...
user avatar
0 votes
0 answers
27 views

Probability of convexity of a polytope in $\mathbb{R}^2$ and possibly $\mathbb{R}^3$?

I have had this question burning in my mind for awhile and was wondering if a more experienced geometer, statistician or probability theorist has any insight: Given the facets of a polytope in $\...
user avatar
1 vote
0 answers
39 views

Separation of polyhedra via Farkas' lemma

Let $A\in\mathbb{R}^{m_1\times n}$, $B\in\mathbb{R}^{m_2\times n}$, $a\in\mathbb{R}^{m_1}$, and $b\in\mathbb{R}^{m_2}$. Consider the intersection of an "open" polyhedron and another closed ...
user avatar
3 votes
0 answers
71 views

Show that the image of the given function is convex

Define a function $f: [-b,b]^d\mapsto \mathbb{R}^d (d>1)$ by $$ f(x)=\int_{[-a, a]^d} \frac{u}{1 + \exp(u^\top x)}du $$ Can we show that the image of $f$ is a convex set? I did some simulations ...
user avatar
  • 1,283
0 votes
2 answers
56 views

Strictly convex function proof

Is the following function strongly convex for $x\succeq 0: \sum_{i} x_i = 1$ and $c_i > 0$ for $i\neq 1$? $$ f(x) = \max_{i\neq 1}f_i(x) = \max_{i\neq 1}\frac{\frac{1}{x_1} + \frac{1}{x_i}}{c_i}. $$...
user avatar
1 vote
0 answers
33 views

A question regarding the proof of Lévy–Steinitz theorem

I am reading the proof of Lévy–Steinitz theorem from ON THE POWER OF LINEAR DEPENDENCIES, which asserts that given a finite set $V$ of the unit ball $B$ of any norm(in $\mathbb{R}^d$) such that $\...
user avatar
0 votes
0 answers
66 views

Statement of Kakutani's Theorem on Convex Bodies

In this paper we find a proof that for every continuous function $f:S^n\to\mathbb{R}$ there exist $n+1$ pairwise orthogonal points $x_0$ through $x_n$ such that $f(x_0)=f(x_1)=\cdots=f(x_n)$. They ...
user avatar
  • 1,569
0 votes
1 answer
46 views

Show that $\min\{\lambda≥0:x\in\lambda K\}=h(K^{*},x)$

Let $K\in\mathscr{C}^n$ with $\overrightarrow{0}\in$ int$K$ and let $h(K,\cdot)=\sup\{<x,y>:y∈ K\}$ be the support function. Also, for $\overrightarrow{x}\in\mathbb{R}^n$ we define $$|\...
user avatar
0 votes
1 answer
36 views

Construct $(P^*)^*$ for a polyhedron

I am trying to solve the following problem: Consider the polyhedron $P = \{x\in \mathbb{R}^3 \mid x_1 + x_2 + x_3 \geq 1, x_j \geq 0 \; j \in [3] \}$. The polar of a set $S$ is defined as $S^* := \{y\...
user avatar
0 votes
0 answers
19 views

Distance between two closed convex bounded non-empty subsets in a CAT(0) space

Let $(X,d)$ be a complete CAT(0) space, where $d$ is the metric on the space $X$. Being CAT(0) here means that for any $x,y\in X$, there is some $m\in X$ such that for any $z\in X$, we have the ...
user avatar
0 votes
1 answer
13 views

Is the intersection of quasi convex sets also quasi convex?

A subset $A$ of a geodesic space $X$ is called quasi convex if there exists a constant $k > 0$ so that if $x,y \in A$, the geodesic joining $x$ to $y$ is in the $k$ neighborhood of $A$. Is it true ...
user avatar
  • 392
0 votes
0 answers
59 views

How to check whether a point is inside the black regions or not?

I have a huge map which is similar to bellow, Problem: I want to find feasible path between two points in the map. Since size of map is huge it takes enormous time to calculate the path. The ...
user avatar
  • 139
1 vote
1 answer
38 views

Efficient algorithms for testing simplicity of a 2D polygon given its vertices?

I'm working on a project that requires me to test if a polygon is convex and I was able to write an algorithm that successfully tests for convexity for simple polygons but fails to provide the correct ...
user avatar
1 vote
1 answer
16 views

How to prove an inequality of gauge norms?

Let $A$ be a compact convex set in $\mathbb R^n$. Let $y\in \mathbb R^n$ be an arbitrary point not belonging to $A$. Let $P$ be a hyper-plane which separates $A$ and $y$. Let $x$ be the projection of $...
user avatar
  • 1,208
0 votes
0 answers
23 views

Can a union of $k$ half spaces be partitioned into $O(k)$ disjoint convex polyhedrons?

Suppose $S=\bigcup_{i=1}^k S_i$, where $S_i=\{x\in \mathbb{R}^d|a_i^Tx\le b_i\}$ is a half space. Can we partition $S$ into $k$ disjoint convex polyhedrons? With the $k$ inequalities defining the $S_i$...
user avatar
  • 49
0 votes
0 answers
15 views

Range of z for convex constraint?

What would the range of z be if this were to be a convex constraint? $2x_1^2 + (2+z)x_2^2 - x_3^2 \leq 5$ I thought it could be approached by applying the two conditions of a convex hull (i.e, the ...
user avatar
  • 1
0 votes
0 answers
50 views

Name for a closed shape that has an interior point such that every line through the point meets the shape's boundary at exactly $k$ distinct points?

Consider a closed shape/set $S \in \mathbb{R}^2$ such that there exists an interior point $(x, y) \in S$ (need not be unique) such that any line passing through $(x, y)$ intersects $S$'s boundary at ...
user avatar
  • 1
3 votes
1 answer
50 views

Two convex sets with same Lebesgue measure of projection at any direction

This question comes from my real analysis class. For any $v=(\cos\theta,\sin\theta) ,\theta\in[0,2\pi)$, let $\pi_{v}(x)=\langle v, x\rangle . $ Let $A, B$ be two bounded open convex sets in $\mathbb{...
user avatar
  • 31
1 vote
1 answer
48 views

Does the closed convex hull of a compact set in the interior of a convex cone is still contained in the interior of the cone?

Let $C$ be a convex cone in a Banach space $X$ with nonempty interior. The set $A\subset {\rm Int}C$ is a compact subset, where ${\rm Int}C$ means the interior of $C$. Denote the closed convex hull of ...
user avatar
  • 23
0 votes
0 answers
28 views

Are half spaces in Hadmard manifold geodesically convex?

Given a Hadamard manifold $M$ (complete, simply connected and of nonpositive curvature) and two points $x,y\in M$ I want to consider the half space $H(x,y)=\{z\in M\mid d(x,z)\leq d(z,y)\}$. I wonder ...
user avatar
3 votes
0 answers
123 views

A linear system optimization

Let $A: \mathbb{R}^n \to \mathbb{R}^d$ be a matrix. Let $$\max_{\|y\|_2 \leq 1 } \min_{\|x\|_2 \leq R}\|Ax-y\|_2 = \epsilon\;.$$ (where $R$ is the radius of the norm ball that $x$ is constrained to). ...
user avatar
  • 395
4 votes
1 answer
73 views

Geometry Question: A property of a convex polyhedron.

I'm trying to interpret a verified solution for the following problem. Show that $v_3+f_3>0$. Here, $v_n$ denotes the number of vertices of a convex polyhedron that meet with $n$ edges, and $f_n$ ...
user avatar
  • 1,248
3 votes
1 answer
71 views

Projection of $\lambda y$ onto a polytope is fixed for sufficiently large $\lambda$?

Le $y\in \mathbb R^n\setminus\{0_n\}$. Let $X\subset \mathbb R^n$ be a compact polytope (intersection of finite half-spaces). For a sufficiently large $\lambda\in \mathbb R_+$, I have the impression ...
user avatar
  • 1,208
0 votes
0 answers
51 views

Is minimum of two convex functions also convex? [duplicate]

We are provided with two convex functions f(x) and g(x) and we are supposed to comment on the convexity of min{f(x),g(x)}. I start out by writing the equations implied when we convexity of f(x) and g(...
user avatar
2 votes
2 answers
83 views

Proof of Straszewicz's theorem

I'm interested in the following result, known as Straszewicz's theorem: (1) For $C$ a compact convex set, the set of exposed points $\text{exp}\ C$ is dense in the set of extreme points $\text{ext}\ ...
user avatar
  • 3,989
1 vote
0 answers
16 views

Convex description of the positive orthant without the y-axis

I know that the following set is convex \begin{equation} X = \{(x,y) \in \mathbb{R}^2 : x>0 ,~ y\geq0 \}~ \cup~\{(0,0)\} \end{equation} i.e. the positive orthant without the y-axis but with the ...
user avatar
  • 15
3 votes
2 answers
57 views

Interior points in a convex set can be represented as convex combination of different points from the set

Can we assume that any interior point $z$ in a convex set $S\subseteq R^n $ be represented by $2$ points $x \in S$ and $y \in S$ such that $z = \lambda x +(1-\lambda)y $, where $x\neq y \neq z$ , and ...
user avatar
1 vote
1 answer
63 views

"Convexity" of a family of distributions

Let $\alpha\in(0,1)$. Consider a family of CDFs $\mathcal{X}$ that contains every CDF $X$ defined on $[0,\infty)$ with increasing hazard rate (IHR) which satisfies $$\mathbb{P}[x>y]=\alpha,$$ where ...
user avatar
  • 175
1 vote
0 answers
21 views

Membership Oracle (MO) for $K+\epsilon B$ given MO for $K$ [closed]

Let $K$ be a convex compact set in $\mathbb{R}^d$. Suppose that a Membership Oracle $\mathcal{M}_{K}$ for the set $K$ is available; given a point $x\in \mathbb{R}^d$, the Oracle returns ''true'' if $x$...
user avatar
1 vote
0 answers
41 views

Request detailed explanation about Stephen Boyd cvxbook-solutions-manual exercise 2.8(a) expressing a set S in the form S = {x | Ax<=b, Fx = g}

cvxbook-solutions exercise page-5 exercise 2.8(a) 2.8(a) $S = \{y_1a_1 + y_2a_2 | − 1 ≤ y_1 ≤ 1, − 1 ≤ y_2 ≤ 1\}, \text{where }a_1, a_2 ∈ R^n$. The following is the solution mixed with my question. ...
user avatar
  • 77
0 votes
0 answers
14 views

Parametrize continuous deformation from one convex body to another

Suppose one has a continuous deformation, $Z(s)$, from an initial zonotope $Z(0)=Z_0$ to a final one $Z(1)=Z_f$, such that $Z(s)\subset Z(s^\prime)$ whenever $s<s^\prime$. I need to define ...
user avatar
  • 65
0 votes
0 answers
19 views

What are the extreme rays of this cone?

I have given the following cone: $P=\lbrace x | Ax \geq 0\rbrace$ where $A=\begin{pmatrix} -1& 1 & 0 & 0 & 0&0\\ 0& -1 & 1 & 0 & -1 & 0\\ 0 & 0 & -1 &...
user avatar
  • 578
0 votes
0 answers
26 views

Best way to describe distance from surface point to projected interior point

Is there a better way to describe the following idea in words? I've been really struggling. My first thought is to call this "skewness" but I don't know where I got that from and it might ...
user avatar
  • 2,058
0 votes
0 answers
25 views

Show that the $l_1$ ball is a convex set based on the convexity of polytope

$P$ is defined as the set of points $x \in \mathbb{R}^d$ satisfying the following constraints: for an integer $m > 0$, for $m$ vectors $a_1, ..., a_m \in \mathbb{R}^d$ and $m$ values $b_i \in \...
user avatar
2 votes
2 answers
71 views

Are these two "Mazur's" theorems the same?

According to Royden: Mazur's Theorem: Let $K$ be a nonempty convex subset of a normed linear space $X$; $K$ is strongly closed if and only if it is weakly closed. According to Wikipedia: Mazur's ...
user avatar
  • 8,284

1
2 3 4 5
24