Questions tagged [convex-hulls]

For questions on the convex hull of a set, a set $X$ of points in a Euclidean space which is the smallest convex set that contains $X$. Consider adding (convex-analysis), or, for questions related to algorithms, (computational-geometry) and/or (discrete-geometry).

Filter by
Sorted by
Tagged with
0 votes
0 answers
20 views

Decomposition of closed convex sets which don't contain any affine lines in a finite demension.

I am studying convex analysis especially the structure of convex closed sets in a finite demension. I am trying to digest this is theorem below, and yes I understand the demonstration and all but I ...
user avatar
  • 125
1 vote
0 answers
15 views

What is an upper bound on the diameter of a convex polytope?

Given a convex polytope defined by $Ax \le b$, with $V = \{ x_1, \ldots, x_n \}$ vertices, I would like to find the maximal distance $\max_{i,j} || x_i - y_i||_2$ as a function of $A$ and $b$ (some ...
user avatar
  • 143
0 votes
0 answers
20 views

Good resources that talk about geodesically convex sets for riemannian manifolds?

Are there any good resources that talk about geodesically convex sets, and in particular convex hulls, for riemannian manifolds? I’ve been wanting to learn more about them, their geometry and ...
user avatar
0 votes
1 answer
53 views

Compact set which isn't convex hull of its extreme points

Consider $\ell^\infty$. Let $$A := \overline{\operatorname{conv}}\left(\left\{\dfrac{e_n}{n}\right\}\right)$$ It's not hard to see that this set is compact (using the Banach-Alaoglu theorem). But how ...
user avatar
  • 5,968
2 votes
1 answer
33 views

Convex hull and optimal solutions

Consider the LP problem: $max$ $3x_1 + 2x_2+x_3$ $s.t$ $3x_1 + 4x_2 + x_3 ≤ 6 $ $2x_1+x_2 + 3x_3 ≤ 5 $ $x_1,x_2,x_3 ≥0$ I have solved the problem and found that the optimal value is 6 at $x=(2,0,0)$. ...
user avatar
  • 47
1 vote
1 answer
147 views

Point in Polytope?

Context: This question is somewhat identical to this on MathOverflow, it’s different in that it only focuses on the formula of the solution to the underlying problem. Suppose I have a convex hull $H$ ...
user avatar
  • 177
0 votes
0 answers
8 views

Can you always find a d-dimension sphere that can circumscribe d-1 polytope

Is it possible to always find a circumscribing sphere in d-dimensions for any polytope in d-1 dimensions? Im thinking of the following papir: https://kenclarkson.org/coresets1.pdf on page 3 they state ...
user avatar
  • 25
0 votes
0 answers
17 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
0 votes
1 answer
26 views

Existence of approximate fixed point

In K.Urai's paper "Fixed point theorems and the existence of economic equilibria based on conditions for local directions of mappings", he claimed the following in Lemma 17: Statement: Let $...
user avatar
  • 425
0 votes
0 answers
10 views

Maximum norm over 'spherical hull' of vectors

Consider $k$ vectors in $\mathbb{R}^n$, $v_1,...,v_k$. Let us define the set $$S_v = \{ x \in \mathbb{R}^n| x = \sum_{i=1}^k \lambda_i v_i, \lambda_i \geq 0, \sum_i \lambda_i^2 = 1\},$$ that is, it is ...
user avatar
  • 1,019
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
1 vote
0 answers
46 views

Fastest way to solve vertex enumeration problem in python

I have a set of 73 linear non-strict inequalities that describe a convex polytope in the 36-dimensional space. All but one of the inequalities are of the form $x>=b$ or $x<=b$. In every but one ...
user avatar
  • 11
0 votes
0 answers
29 views

Shortest helical path with bumps on a cylindrical surface : 3D Convex 'Line' instead of hull?

I am studying the effect of fiber overlap during filament winding on a cylindrical surface. Every time a fiber crosses over another fiber, due to the thickness of the fiber under it, it 'bridges' for ...
user avatar
2 votes
1 answer
135 views

Intersection of convex hulls

I have two polyhedral sets $\mathscr{P}_1, \mathscr{P}_2,$ defined as convex hulls $$\mathscr{P}_1 = \mbox{conv} \left\{ v_{1},\dots, v_{N} \right\}, \qquad \mathscr{P}_2 = \mbox{conv} \left\{ w_{1},\...
user avatar
0 votes
2 answers
30 views

Build an explicit polyhedral representation of $\operatorname{Epi}(f)$

Let $f : \mathbb{R}^n \rightarrow \mathbb{R}$ be defined by $f(x) = \max\limits_{1\leq i < j \leq n} \{ |x_i| + |x_j| \}$. Furthermore, let $\operatorname{Epi}(f) = \{ [x; t] \; : \; f(x)\leq t\}$. ...
user avatar
0 votes
0 answers
28 views

Convex hull and bounding circle of a set of points on a sphere?

Given a finite set of random points on the unit sphere (defined in spherical coordinates), are there formulas giving the center and radius of the smallest circle (on the sphere) that contains all of ...
user avatar
  • 101
1 vote
0 answers
20 views

If intersection of closed convex hull is singleton that implies weak convergence

$X$ be a locally convex topological vector space. $\{x_n\}$ converge weakly to $x$ iff $x$ in the closed convex hull of every subsequence of $\{x_n\}$. I'm able to show the only if part that is if $...
user avatar
0 votes
0 answers
7 views

How to decide which operator gives a tighter distribution of points?

Say I have two matrix operators in $\mathbb R^n$ which maps points in $(a,b)$ to points strictly in $(a,b)$, i.e., the more I apply the two operators the more the set (a,b) shrinks or the result of ...
user avatar
  • 35
0 votes
0 answers
32 views

Convergence of convex hulls of a finite set

Setup: Let $B=\text{conv}\{x_1,..,x_k\}$ be the convex hull of $k$ points in $\mathbb{R}^m$. Consider $k$ sequences $(x_i^n)_{n\in{\mathbb{N}}}$ converging to the corners $x_i^n\rightarrow x_i$ for $i=...
user avatar
  • 106
0 votes
0 answers
38 views

Show that a convex hull of a set of vectors contains a positive vector.

Notation: $coS$ is the convex hull of a set, $e_{i}$ is a standard basis vector with the ith coordinate equal to 1, $\vec{0}$ is the n-dimensional zero vector. Let $S = \{s^{i},i \in {1,...,n}\}$ be a ...
user avatar
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
1 answer
38 views

Vertex is an extreme point

Given a polyhedron $P \subseteq \Bbb R^n$, a point $x \in P$ is called a vertex if there exists a vector $c$ such that $c · x > c · y$ for all $y \neq x \in P$. A point $x \in P$ is called an ...
user avatar
  • 996
0 votes
0 answers
42 views

Convex Hull with Buffer Radius

I am using a convex hull (via a Delauney Triangulation) around a point cloud to define a given region on a manifold. The problem I encountered was that the triangulation will never accurately describe ...
user avatar
  • 1
0 votes
0 answers
28 views

$A\subset X$ is sequtially compact. Prove that $\overline{Conv A}$ is also sequentially compact.

Suppose $X$ is a Banach space, $A\subset X$ is sequtially compact. Prove that $\overline{Conv A}$ is also sequentially compact. $\overline{Conv A}$ is the smallest closed and convex set which ...
user avatar
  • 1,153
1 vote
0 answers
52 views

On an extension of Gauss Lucas

let $f(z)\in\mathbf{C}[z]$ be a nonzero polynomial. by the Gauss-Lucas theorem we have that $$\text{conv}(\{\text{roots of }f\})\subseteq\bigcap_{F'=f}\text{conv(\{roots of F\})}$$ Question. can the ...
user avatar
  • 115
0 votes
0 answers
10 views

How to obtain the time-invarient set which approximates a set of time-varying convex polygons?

I have a set of time-varying convex polygons each representing the solution space at a particular discrete time step. As the next step, I am in need of obtaining a time-invarient convex set which ...
user avatar
0 votes
2 answers
27 views

Let $(x_d), (y_d)$ be nets such that $x_d \to a$ and $y_d \in \overline{\operatorname{conv} \{x_e \mid e \ge d\}}$. Then $y_d \to a$

In solving Ex 3.13.1 in Brezis's book of Functional Analysis. I come across below claims. Let $E$ be a locally convex t.v.s. and $(x_d)_{d\in D}$ a net in $E$ such that $x_d \to a\in E$. Let $$ X_d :=...
user avatar
  • 1,153
3 votes
2 answers
58 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
0 votes
0 answers
16 views

The image of an open set is a subset of the convex hull of the image of the boundary

Consider a $C^1$ function $f : \bar{\Omega} \to \mathbb{R}^N$, where $\Omega$ is a smooth open set of $\mathbb{R}^d$ such that for every smooth open subset $\Omega'\subset \Omega$, we have $$ f(\Omega'...
user avatar
  • 49
0 votes
0 answers
17 views

Is the 2D projection of the maximum volume inscribed ellipsoid still inside the 2D projection of the polyhedron?

I have a set of points for which I computed the convex hull (which is a Polyhedron). I then computed the maximum volume inscribed ellipsoid of it. Because this problem is six-dimensional, plotting for ...
user avatar
3 votes
4 answers
50 views

Show that convex hull of $\{x_j\}_{j =1}^N \subseteq \mathbb{S}^{n-1}$ meets $\mathbb{S}^{n-1}$ only in the $x_j$

Let $x_1, \dots, x_N$ be a finite collection of distinct points on the unit sphere $\mathbb{S}^{n-1} \subseteq \mathbb{R}^n$. Consider the convex hull $C$ of these points, defined to be $$ C = \{ \sum^...
user avatar
  • 4,458
-1 votes
1 answer
65 views

What is a dimension of a convex hull?

Let $S$ be a set of data points in $E^d$, a real Euclidean space of dimension $d$. What would be the dimension of the convex hull of that data? In general, what is the definition of the dimension of ...
user avatar
  • 3
1 vote
1 answer
68 views

Interior of a convex cone and Carathéodory theorem

Let $X$ be a normed $\mathbb R$-vector space, $S\subseteq X\times\mathbb R$ and $$K=\left\{\sum_{i=1}^k\lambda_ix_i:k\in\mathbb N,x_i\in S,\lambda_i\ge0\right\}.$$ In a lecture note, where the case $X=...
user avatar
  • 12.8k
0 votes
1 answer
64 views

In $\mathbb{R}^\mathbb{N}$: Simultaneous distance reduction to points in $A$ possible iff outside closed convex hull spanned by $A$

I'm working on a problem, and have managed to reduce it to this proposition: Consider $\mathbb{R}^\mathbb{N}$ with the following distance function that has $\infty$ as a possible value: $d(x,y)=\sum_{...
user avatar
  • 964
3 votes
1 answer
47 views

Convex $k$-gon containing $k+1$ points must contain $k+2$ points

Let $\{a_1,a_2,\cdots, a_{2k+2}\}$ be vertices of a convex $(2k+2)$-gon, labelled counterclockwise. Let $A = \{a_1,a_3, \cdots, a_{2k+1}\}$ be the subset labelled by odd integers. Intuitively, any ...
user avatar
2 votes
0 answers
39 views

Characterize convex sets that are the convex hull of their extreme points

The famous Krein-Milman theorem states that every compact convex set in a topological vector space is the convex hull of its extreme points. Note, however, that many convex sets exist in $\mathbb R^n$ ...
user avatar
  • 327
1 vote
0 answers
25 views

How can we exclude vertices of a compact polyhedron and represent it as a convex hull?

It is known that every compact (closed and bounded) polyhedron $P$ can be written as a convex hull of finitely many points, i.e., $\text{conv}\{x_1, \dots, x_m\}$. Questions How can I make sure that, ...
user avatar
  • 941
0 votes
1 answer
35 views

Sum of restricted strictly convex functions

Suppose that $\boldsymbol{x}\in\mathbb{R}^p$. Also, assume $\Omega\subseteq \{1,2,\ldots,p\}$ is a subset of the indices, and $\Omega^c$ denotes the complement of $\Omega$. The notation $\boldsymbol{x}...
user avatar
  • 61
3 votes
1 answer
44 views

Proof that $\left(\frac{1}{x}, \frac{1}{y}\right)$ is a convex region if $(x, y)$ is

I'm trying to convince (prove) myself that if a set $S \subset \mathbb{({R^+})^2}$ is a convex region, then $S' := \left\{ \left(\frac1{x}, \frac1{y}\right) ; (x, y)\in S \right\}$ is also a convex ...
user avatar
  • 3,353
0 votes
0 answers
47 views

Max/min values over convex hulls.

Let $\mathbf{v}_1,\dots,\mathbf{v}_r$ be vectors in a Euclidean space $\mathbf{V}$. Let $f \colon \mathbf{V} \to \mathbb{R}$ be a linear function. Prove that $f$ has both a maximum and a minimum value ...
user avatar
0 votes
1 answer
55 views

Prove convex hull is a compact set

Let $\mathbf{v}_1,\dots,\mathbf{v}_r$ be vectors in a Euclidean space $\mathbf{V}$. Prove that the convex hull $\mathrm{Conv}(\mathbf{v}_1,\dots,\mathbf{v}_r)$ is a compact set. I believe the convex ...
user avatar
2 votes
0 answers
21 views

Sufficient condition for convex conjugates (does one imply the other?)

We say $(f_1,f_2,\cdots,f_N)$ a convex conjugate if for any $i=1,2,\cdots,N$ and any $x_i\in\Bbb R^d$, we have: $$f_i(x_i)=\sup\left\{\sum_{k=1}^{N}\sum_{j=k+1}^N x_k x_j - \sum_{j=1,j\neq i}^N f_j(...
user avatar
6 votes
0 answers
141 views

Distance between point and convex hull in high dimensions

I am trying to develop an intuition for the properties of the convex hull of a set of points in high ($d>20$) dimensions. Consider a set of $n$ data points which are iid distributed according to ...
user avatar
  • 160
0 votes
0 answers
43 views

How to prove the Carathéodory theorem?

How to prove the following theorem: Theorem (Carathéodory) : Let $S\subset\mathbb{R}^{n}$. Any $x\in\mathbf{conv}(S)$ can be represented as a convex combination of at most $n+1$ points. I just started ...
user avatar
0 votes
1 answer
43 views

Jordan decomposition functional $C^*$-algebra [closed]

Consider the following fragment from the thesis Injective and Semidiscrete von Neumann Algebras by Rasmus Sylvester Bryder: Why is the boxed equality true? In particular, I don't see why the right ...
user avatar
  • 985
6 votes
1 answer
86 views

When is the smallest point on a hull a convex combination of the smallest vertices?

Let $x_1, \dots, x_n\in\mathbb{R}^d$ be a finite set of points and denote the convex hull by $H$. Assume that $0\not\in H$ and also that each $x_i$ is an extreme point, meaning that it cannot be ...
user avatar
  • 5,222
1 vote
1 answer
27 views

convex hull and convex combination

Let $X\subseteq R^d$ and $u\notin conv(X)$. I want to prove that any $y\in conv(X\cup u)$ can be written as $\lambda u + (1 − \lambda)x$ for some $x \in conv(X)$ and $λ \in [0,1]$. I intuitively get ...
user avatar
  • 11
1 vote
1 answer
48 views

Expanding a convex set to a convex set with nonempty interior, while maintaining disjointness from a point

Suppose $X$ is a finite-dimensional normed space over $\mathbb{R}$. Let $\emptyset\neq M\subseteq X$ be a convex set with empty interior, and let $x\in\overline{M}\backslash M$ be a point on the ...
user avatar
  • 21
4 votes
2 answers
88 views

A set of points is contained in a sphere $S$. When is $S$ also the circumsphere?

Given points $p_1,\ldots,p_n\in\Bbb R^d$ so that all of them are contained in a common sphere $S\subset\Bbb R^d$ (by which I mean the usual $(d-1)$-dimensional sub-manifold of $\Bbb R^d$). Note that $...
user avatar
  • 935
0 votes
0 answers
24 views

Norm of vectors in the closed convex hull

Let $S$ be a nonempty closed bounded subset of a normed vector space $(X,\|\cdot\|)$. Denote by $\overline{\mathrm{co}}(Y)$ the closed convex hull of a set $Y$. Question. Is it true that $\{\|x\|: x \...
user avatar

1
2 3 4 5
11