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
1 vote
0 answers
33 views

Given a set of points forming a convex hull, is it possible to find a specific hyperplane?

I have a set of points in $\mathbb{R}^n$ and I can use some convex hull algorithm to find the convex hull of this set and the corresponding extreme points (vertices). My goal is to find the supporting ...
jerry's user avatar
  • 67
0 votes
0 answers
63 views

Convex hull of a set is equivalent to the convex hull of the extreme point of the set?

Assume $X$ is a compact set (not necessarily convex). If the following equality holds true? $$\text{Conv}(X)=\text{Conv}(\text{extr(X)})$$ where $\text{extr}$ means the extreme point of $X$. The ...
jerry's user avatar
  • 67
0 votes
0 answers
56 views

Convex hull of union over extreme points of hypercuboids is equivalent to convex hull of extreme point of a union over hypercuboids?

Assume that $X,Y,Z$ are three hypercuboid with the same dimension $k$. Specifically, we have $X=\{x_1,x_2,...,x_k:0\leq x_i\leq c_i, \forall\,i\}$ and $Y=\{y_1,y_2,...,y_k:0\leq y_i\leq b_i, \forall\,...
jerry's user avatar
  • 67
1 vote
1 answer
35 views

Affine Combinations and Span

I was reading a bit of convex analysis and came across this problem. Let $S$ be convex. Let $A$ be the set of finite affine combinations of points in $S$ (i.e. finite linear combinations whose weights ...
John Atwood's user avatar
0 votes
1 answer
22 views

Convex Hull Point Equality

I ran into the following problem on point equality in convex hulls. Let $S$ be a subset of $d$-dimensional Euclidean space. Suppose that points $p_1,p_2$ do not lie in the convex hull of $S$, but $p_i$...
Morgan Zariski's user avatar
9 votes
0 answers
97 views

Are convex objects determined by their silhouettes?

Informally, the silhouette of a 3D shape is a viewpoint-dependent 2D projection of it. You might imagine looking at several silhouettes and attempting to construct the overall shape. My question is ...
user326210's user avatar
  • 17.2k
1 vote
1 answer
114 views

Efficiently find the intersection of a ray with a convex hull

In some other question regarding basis selection a surprising solution came up, where we construct the convex hull of the given points and then shoot a specific ray from the origin. The corners of the ...
Moritz Seppelt's user avatar
1 vote
0 answers
78 views

Does unique convex combination imply affine independence?

Why we need affine independent to ensure the unique representation of a vector from convex hull. As far as I understood, the converse of the theorem is not true. In other words, if any vector 𝑣 is in ...
fezaninsonu's user avatar
0 votes
0 answers
85 views

Closed convex hull of a set is the unit ball.

Let $X$ be a (real) Banach space and $A \subseteq X^{*}$ some weak*-compact subset of a unit ball in $X^*$. Furthermore, assume that for any functional $f \in A$, we have $-f \in A$. Now we know that, ...
the_dude's user avatar
  • 460
1 vote
0 answers
41 views

closed convex hull, closure of convex hull and convex hull of closure

Let $X$ a topological vector space and $A\subseteq X$ a subspace. Let $co(A)$ the convex hull of $A$ (the smallest convex subspace containing $A$) and $\overline{co}(A)$ the closed convex hull of $A$ ...
marc's user avatar
  • 181
0 votes
1 answer
27 views

If $X$ is contained in one side of the hyperplane $H$, then $\text{conv}(X) \cap H = \text{conv}(X \cap H)$

I am trying to prove the following result: Let $X$ be a subset of $\mathbb{R}^n$ and $H=\{x \in \mathbb{R}^n:\langle x,u\rangle=\alpha\}$ be a hyperplane with normal vector $u$ such that $X \subset H^...
ImHackingXD's user avatar
3 votes
0 answers
62 views

Minimum number of points to have a point inside every triangle formed by $n$ points

Place $n$ points in a general position on the plane. Call a set $S$ of any points stabbing if every triangle formed by the $n$ chosen points contains at least one point from $S$ in its interior. For ...
Kangaroo976's user avatar
1 vote
0 answers
12 views

One-to-one Correspondence of Facets of a Polytope [closed]

If the facets of a polytope $A$ are in one-to-one correspondence with the members of a finite set $X$ and the facets of a polytope $B$ are also in one-to-one correspondence with the members of $X$ (ie....
Tom's user avatar
  • 1,270
2 votes
0 answers
27 views

Techniques for convex optimization over a vertex-representation of a polytope?

I have a convex optimization problem where the feasible region is defined as the convex hull of a set of vertices. Even though the vertex set is in the low dozens of points, finding the half-space (H-...
Scott McKuen's user avatar
0 votes
0 answers
53 views

Equivalent definition of closed convex hull in real normed spaces

Let $X$ be a real normed space and $A \subset X$ a nonempty subset. We define the closed convex hull of $A$ to be the subset $$\overline{\text{conv}}(A):=\bigcap \{B\subset X:A\subset B, B \text{ is ...
mathematica's user avatar
2 votes
0 answers
50 views

Defining a convex "hole"

How could we define the idea of the inverse of the convex hull? To clarify, not what is the innermost convex hull without recursively drawing and removing convex hulls, but maximizing a convex shape ...
IainMcE's user avatar
  • 21
0 votes
0 answers
20 views

Convex hull of points in convex set $P$ is subset of $P$?

Given a convex polytope $P \subset \mathbb R^d$, suppose $p_1, \dots, p_t \in P$. Denote by $\text{Conv}(\{p_1, \dots, p\})$ the convex hull of $\{p_1, \dots, p_t\}$. Do we have $\text{Conv}(\{p_1, \...
caitlin's user avatar
  • 103
2 votes
0 answers
58 views

Given $n$ random points in a disk/square, on average how many progresively smaller convex hulls can be drawn?

Given $n$ points placed uniformly and at random in a disk/square, on average how many convex hulls can be drawn if, every time the convex hull is drawn, every point on that convex hull is deleted? ...
Lieutenant Zipp's user avatar
2 votes
0 answers
57 views

Is every geodesic triangle contained in a surface?

Let $M$ be an $n$-dimensional Riemannian manifold, $n \ge 3$. Let $T$ be a geodesic triangle in $M$. Does there exist a (smooth) $2$-dimensional embedded submanifold $S \subset M$ such that $T \...
Asaf Shachar's user avatar
  • 25.1k
1 vote
0 answers
60 views

If p is a vertex on the convex hull of S, then the farthest-point voronoi region of p is not empty [closed]

I am given a set $S$ of points and I want to prove that for any point $p$ in $S$, the farthest-point voronoi region of $p$ is not empty if and only if $p$ is on the convex hull of $S$. I denote ...
ali nakhaee's user avatar
2 votes
0 answers
22 views

Nonsmooth analysis: Need help clarifying a step in the proof that $co D^\ast u(x) = \partial f(x)$

I am reading the book optimization and nonsmooth analysis by Frank.H Clarke and there's a step I'm stuck in the proof of theorem 2.5.1. So I'll write the definitions first. We work in $\mathcal{R}^n$ ...
Franlezana's user avatar
0 votes
1 answer
57 views

Intersection of convex hulls of two disjoint sets

Suppose that I have a finite set in $\mathbb R^n$, $A:=\{x_1,\ldots,x_n\}$. I want a condition on this set such that $co(S) \cap co(T) = \emptyset$ for any $S,T \subset A$ with $S \cap T = \emptyset$, ...
avk255's user avatar
  • 409
1 vote
0 answers
24 views

Clipping an n-dimensional polygon with a halfspace

Assume that I have a convex polygon in $n > 3$ dimensions, defined by a set of $m$ vertices $\{p_1,\dots,p_m\} \in \mathbb{R}^{n}$. Currently, I have defined my polygon as a set of edges between ...
J.Galt's user avatar
  • 961
0 votes
0 answers
22 views

Do linear optimization problems with some infinite coefficients have convex solution spaces?

I am working with an integer linear optimization problem of the form Find $\vec{x}$ such that $\mathbf{A}\vec{x} < 0$ and such that the sum of the entries of $\vec{x}$ is as small as possible. ...
user326210's user avatar
  • 17.2k
0 votes
0 answers
22 views

Show that $conv\{\partial_x g(x,z')|z'\in \mathcal{A}(x)\}\subseteq\partial f(x)$

Let g(·,·):$\mathbb{R}^{n+m}\rightarrow \mathbb{R}$ be a convex function. Let Z be a nonempty compact convex subset of $\mathbb{R}^m$. The function $f(x)=min_{z\in Z}g(x,z)$. It is easy to prove that $...
Zongfy's user avatar
  • 1
1 vote
1 answer
46 views

How to determine if a linear combination of $n$ variables is inside the convex hull of that $n$ variables

I know there is a common answer that the weights used to make a linear combination should be non-negative and sum up to one. But I think this condition is just a sufficient condition, not a sufficient ...
Xu  Yang's user avatar
  • 13
0 votes
0 answers
22 views

Proving that if $n$ hemispheres cover a sphere, it is possible to choose 4 hemisphere that also cover the sphere.

The question is taken from Cool Induction Problems. Quoting: (**) A sphere is covered with some number of “caps” which are hemispheres. Prove that it is possible to choose four hemispheres, and ...
by24's user avatar
  • 983
1 vote
1 answer
51 views

What explains the reasoning behind the assumption in the proof of convexity for a collection of points?

I would like some clarification on a proof about convexity. This is from Boyd and Vandenberghe's Convex Optimization book. and it has been answered before. It's been over 10 years since the questions ...
Jxson99's user avatar
  • 158
0 votes
1 answer
91 views

Writing a point in convex hull as convex combinations of determined points

I know the Caratheodory's theorem states that if a point $x$ lies in the convex hull $Conv(P)$ on a set $P \subset R^{d}$, then $x$ can be written as the convex combination of at most $d + 1$ points ...
wsz_fantasy's user avatar
  • 1,546
1 vote
0 answers
13 views

The facet-defining inequalities for a single resource scheduling problem

Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions: $$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
A.Omidi's user avatar
  • 137
1 vote
0 answers
134 views

Question about Interior of $S^n_+$ (semi definite positive matrices)

I read this link Interior of $S^n_+$ (semi definite positive matrices) and I have a question about What would be the relative interior of $S^n_+$ I prove that $S^n_+$ it's a is a closed pointed convex ...
ruka's user avatar
  • 116
2 votes
0 answers
21 views

Proving that a given set defined by an inequality is convex

I want to prove that the convex hull of a region defined by the following inequality is convex: $$(y-z)^2 -4x w \geq 0$$, where $x + y + z + w = 1$ and $x, y, z, w \geq 0$. I tried using the Hessian ...
Cicero 's user avatar
0 votes
0 answers
68 views

About the Convex Hull of a the image of a function

Let $ f \in L^1_{loc}(\mathbb R^n)$ and $ \varphi $ a mollifier, consider $\varphi_{\varepsilon}:=\frac{1}{\varepsilon ^n} \varphi \left( \frac{x}{\varepsilon} \right)$ show that $f * \varphi_{\...
C L 's user avatar
  • 191
0 votes
0 answers
18 views

Help me understand the dimensionless Caratheodory Theorem in a paper

I found this very interesting paper online which yields a version of Caratheodory's Theorem independently of its dimension (Theorem 1.1 therein), i.e. Let $P$ be a set of $n$ points in $R^d$, $r ∈ [n]$...
samabu's user avatar
  • 713
3 votes
1 answer
150 views

Is this operator always contained in the convex hull for closed sets?

Looking through the window of a bus at night a long time ago I got to think of the following. Given a subset $X\subseteq \mathbb{R}^{n}$ (assume $n\in\mathbb{N}\setminus\{0\}$), define its silhouette $...
AnyDisplayName's user avatar
0 votes
0 answers
40 views

How to find the inscribed and circumscribed circles from convex region?

Let $\mathbf{P}(t)$ be a piecewise bezier curve of degree $p$, which defines a jordan curve in the plane such the interior region $D$ is convex. Question: How can I find the external $C_e$ and ...
Carlos Adir's user avatar
  • 1,292
0 votes
0 answers
32 views

Is there such a thing as a convex polytope defined over a mixed-variable space: $\mathbb{Z}^m \times \mathbb{R}^n$

I am currently learning about polytopes and I have reached the stage of convex polytopes. Wiki says that a convex polytope is a special case of a polytope, having the additional property that it is ...
Astrid's user avatar
  • 722
0 votes
1 answer
40 views

What is the convex hull of nonconvex polytopes defined by mixed integer linear inequalities (with only binaries)

Define $$S=\{(x_1,x_2,y)|0\le x_1\le y\overline{x},0\le x_2\le (1-y)\overline{x},x_1,x_2\in\mathbb{R},y\in\{0,1\}\},$$ $\operatorname{conv}(S)$ is the convex hull of $S$. $\le$ is componentwise. $\...
Ruihao Wang's user avatar
1 vote
1 answer
55 views

I need help understanding a step in this paper about convexity of n random points in a square [closed]

In this paper "Probability that n random points are in convex position" by Pavel Valtr I followed through with everything until in page 4 when he introduces the idea of a property $P_{i,j}$ ...
Nishchal Bhat's user avatar
0 votes
0 answers
40 views

Convexity of spherical curves

Let $\gamma$ be a smooth curve in $\mathbb{R}^{3}$. We say that $\gamma$ is convex if it lies on the boundary of its convex hull. Recall that the convex hull of $\gamma$ is the set of all convex ...
user avatar
2 votes
0 answers
77 views

Convex hull of convex space curve

Let $\gamma$ be a smooth closed curve $\mathbb{R}^{3}$. We say that $\gamma$ is convex if it lies on the boundary of its convex hull, which we denote by $\mathrm{conv}(\gamma)$. I know that the convex ...
user avatar
1 vote
1 answer
43 views

Characterization of convex hull in terms of (in)equality properties

Let $A \subseteq \{0,1\}^n$ be a set of vectors that satisfy some (in)equality properties, e.g., $$ \begin{aligned} A &= \left\{ x \in \{0,1\}^n : x_1 = x_2 \right\} \\ A &= \left\{ x \in \{0,...
Y.Z.'s user avatar
  • 921
0 votes
0 answers
10 views

Fast evaluation of max-reduced dot product in hull test

$$0 \le i<m$$ $m > 1000$ is the number of points for which a hull containment test is performed. $$0 \le j < n$$ $n > 1000$ is the number of faces on a convex hull. $0 \le k \le 3$ is the ...
Reinderien's user avatar
0 votes
0 answers
27 views

Relation between the inclusion of a point in a convex hull and inclusion of the subdifferentials of a convex function at that point?

I'm looking to prove a intuitive enough propriety of the subdifferentials of a convex function : let $f : E \to \mathbb{R}$ be a convex function, $n \in \mathbb{N}$ and let $p_1,p_2,\dots,p_n \in E^n$....
Ivan's user avatar
  • 1
1 vote
1 answer
34 views

Quaternionic numerical range of a class of matrices

I need to characterize the quaternionic numerical range of matrices of the form $$\begin{bmatrix} r & p \\ 0 & -r\end{bmatrix}$$ where $r$ is a positive real number and $p$ is a quaternion. ...
Abhilash Saha's user avatar
3 votes
1 answer
103 views

Extreme points under closure operators

Let us introduce the following definition: Let $X$ be a set. A mapping $f: \mathcal{P}(X) \rightarrow \mathcal{P}(X)$ is said to be a closure operator if for all subsets $S, T \subseteq X$, the ...
Tian Vlašić's user avatar
0 votes
0 answers
38 views

Convex hull of a set of $2^{n-2}$ points without a convex subset of $n$ points

I was recently looking at the happy ending problem, and on the linked Wikipedia page, there is the following conjecture (the Erdos-Szekeres conjecture), which states the following: The smallest ...
Varun Vejalla's user avatar
2 votes
0 answers
53 views

Is convex conjugate infinite outside closed convex hull of gradients?

This question is related to Convex conjugate of a differentiable function Let $f : \mathbb{R}^n \to \mathbb{R}$ be convex and differentiable everywhere. For $y \in \mathbb{R}^n$, define $$f^*(y) := \...
I love pineapple coffee's user avatar
1 vote
2 answers
99 views

About density matrices as both the vertices of a convex hull and the basis of a matrix space

Given $n$ density matrices $D_1, \dots, D_n$, that is, $D_i$ is positive semi-definite and $\operatorname{Tr}(D_i)=1$ for all $1\leq i\leq n$. Suppose that $D_1, \dots, D_n$ are linearly independent. ...
Thinkpad's user avatar
  • 383
0 votes
0 answers
33 views

Lie algebra of the convex hull of extreme points?

I have stumbled across the following meta-question while working on a research problem. I have a compact, convex set, $\mathcal{K}$. Be Krein-Milman, any element in $\mathcal{K}$ can be written as ...
user82261's user avatar
  • 1,169

1
2 3 4 5
13