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).
575
questions
3
votes
1
answer
24
views
Suppose $P_1$ and $P_2$ are two $n$-dimensional convex polytopes. Does $\partial P_1 \subseteq\partial P_2$ imply that $P_1 = P_2$?
Given two convex polytopes $P_1$ and $P_2$ with the same dimension, I want to know if the boundary of $P_1$ (denoted $\partial P_1$) being contained in the boundary of $P_2$ (denoted $\partial P_2$) ...
- 1,564
0
votes
2
answers
46
views
Linear and convex independence of "probability vectors"
We have vectors $v_1,\dots,v_n$ in $\mathbb{R}^m$ with $n \leq m$. Each $v_i$ is a "probability vector" in the sense that its entries are all non-negative, and sum to one.
Suppose that $\{...
- 65
5
votes
0
answers
74
views
Convexification of $\frac{a}{12}\,(x^4-2\,x^2)+b\,x$
Let $f:\mathbb R\to\mathbb R$
$$f(x)=\frac{a}{12}\,(x^4-2\,x^2)+b\,x\,$$
with parameters $a,b>0\,$. $f$ is concave on the interval $\left[-\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}\right]$ and convex ...
- 783
2
votes
1
answer
67
views
Prove the affine hull of polyhedron is $\{x\in\mathbb{R}^n|\langle a_i,x\rangle\leq b_i,\forall i\in I\}$
Given $a_i\in\mathbb{R}^n,b_i\in\mathbb{R},1\leq i\leq p$, define a polyhedron $P=\{x\in\mathbb{R}^n|\langle a_i,x\rangle\leq b_i,1\leq i\leq p\}$ and $I=\{i|\langle a_i,x\rangle=b_i,\forall x\in P\}$,...
- 619
0
votes
1
answer
22
views
Generate cycle graph from vertices
I have K vertices and I need to connect them to form a graph. I am currently generating a complete undirected graph that looks like these:
However, I only need the ...
- 113
0
votes
1
answer
50
views
Variant of Erdos-Szekeres theorem
I'm having trouble proving the following theorem:
For all $n \in \mathbb{N},$ $\exists$ $N \in \mathbb{N}$ such that any set of $N$ points in the plane will contain either a convex $n$-gon or $n$ ...
- 107
1
vote
1
answer
50
views
How to determine the 3d shape formed by intersecting planes
Question
How can I optimally get the list of vertices for the 3d shape (a convex hull) formed by a set of intersecting planes in 3d space that contains all feasible solutions. Assuming that a 3d shape ...
1
vote
1
answer
31
views
Maximum distance between a point in the convex hull of $A$ and its closest neighbour in $A$
I have a bounded set $A \subset \mathbb{R}^{n}$. I'm trying to compute the maximum distance (or an upper bound to it) between a point belonging to the convex hull of $A$ and its closest neighbour in $...
- 13
1
vote
1
answer
33
views
Join vs. Convex Hull
Consider two subsets of $\mathbb{R}^n$, $A$ and $B$. Their join is the set of line segments connecting a point in $A$ to s point in $B$. That is, $x\in\text{Join}(A,B)$ if and only if $x=\lambda a+(1-...
- 11
1
vote
1
answer
35
views
Reversal of inequality sign in Jensen's inequality
I am given a set of coefficients such that the affine combination $\{x_1, x_2, ..., x_n \} \notin conv(x_1, x_2, ..., x_n)$. How do I prove that under such given conditions the Jensen's inequality ...
- 11
1
vote
0
answers
16
views
The concept of Alpha parameters (in the context of alpha shapes)
Please clarify the concept of Alpha parameters.
A simplest non-degenerate example computing alpha shapes, possibly just with 3 or 4 points would help.
The following sources seems to have conflicting ...
- 111
1
vote
0
answers
32
views
A lower bound on the number of integer lattice points inside a 0-symmetric convex body
I've been doing some reading around the number of points of $\mathbb{Z}^n$ inside an arbitrary rank $n$, $0$-symmetric convex body $K$. In particular, I came across Blichfeldt's remarkable bound:
$$
\...
- 658
1
vote
0
answers
16
views
Isolate downward-facing faces of a convex hull
long time fan / first time poster here!
My question: is there an efficient algorithm for isolating just the downward-facing faces of a 3D convex hull?
In two dimensions, if one draws a line from the ...
0
votes
1
answer
61
views
Is the average area of a random $n$-dimensional convex hull decreasing with $n$?
I calculate the area of the convex hulls of $n+1$ random points in a unit $n$-cube for $n$ = $3$ to $10$. (I use scipy.spatial.convexhull).
For each $n$, I generate $1000$ sets to get the average area ...
1
vote
0
answers
48
views
Proof Boundedness of Voronoi Cells
I have to proof, that given a set of Points P, to decide if the Voronoi Diagram of P has bounded Voronoi Cells.
I have read about, that a Cell is unbounded if it is on the Convex Hull of P. In that ...
- 11
0
votes
0
answers
32
views
How to prove that a set of lines have the same convex hull as a set of the line endpoints with induction
This is a question 1.6a from the book Computational Geometry Algorithms and Applications
1.6 In many situatuions we need to compute convex hulls of objects other than points.
a. Let S be a set of n ...
- 11
0
votes
0
answers
34
views
Is the following function convex?
Let $y \in \mathbb{R}^d$ be arbitrary, and let $f:S \to \mathbb{R}$ be defined by $f(M) = \min_{x : x^TMx = 1} {\left\lVert x - y \right\rVert}_2 $ where $S$ is the set of all symmetric positive semi ...
2
votes
1
answer
70
views
Ratio of largest to smallest distance in a set of six points is $\ge \sqrt 3$?
Here is problem A1 of 25th Putnam 1964.
Let $A_1, A_2, A_3, A_4, A_5, A_6$ be distinct points in the plane. Let $D$ be the longest distance between any pair, and $d$ the shortest distance. Show that $...
- 4,508
0
votes
0
answers
28
views
Objects that can be 'pulled apart' without touching each other
Is the following definition of objects (defined by compact sets) which may be 'pulled apart' without physically touching each other acceptable?
Two compact sets $A, B \subset \mathbb{R}^3$ are said to ...
- 148
0
votes
0
answers
66
views
Is the boundary of the convex hull of a closed, smooth surface in $\mathbb{R}^3$ also a closed, smooth surface?
I have recently been looking for results giving insight into whether the statement in the title is true or only sometimes true. Does anyone know of any results and/or papers or books related to this ...
- 148
1
vote
0
answers
29
views
Is there a short representation for the convex hull of all row and column permutations of a matrix?
Suppose $S$ is the set of all $n\times n$ permutation matrices. For a matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ define the set $P(\mathbf{A})$ as the set of all equal row and column permutations of ...
- 11
0
votes
0
answers
47
views
Number of faces of a certain convex hull in $\mathbb{R}^4$
Imagine a convex hull of n points in $\mathbb{R}^4$. The coordinates of the vertices of the convex hull are as follows:
$$p_a = (a, a^2, a^3, a^4) \ \ \text{for} \ \ a = 1, ..., n$$. I want to prove ...
0
votes
2
answers
29
views
maximum of a convex, continuous function
Let $f:\mathbb R^d\rightarrow \mathbb R$ be a convex function and $M\subseteq \mathbb R^d$ compact. Show that $f$ has its maximum over $M$ with $\max\{f(x):x\in conv(M)\}=\max\{f(x):x\in M\}$ where $...
- 139
0
votes
0
answers
21
views
Excluding inner shapes with the alpha-shape algorithm
I am using the alpha shape algorithm based on the Delaunay triangulation to find the outer border of a set of point in a parametric way. Suppose this is the result:
Is it possible to use the same (or ...
- 111
0
votes
0
answers
33
views
Can I slightly modify a convex function so that it has a unique minimum point and the difference is uniformly bounded?
Consider a convex function $f: U \to \mathbb{R}$ where $U \subset \mathbb{R}^{m}$ is convex compact. Such convex function may have multiple minimizers, i.e., $\arg \min\limits_{u \in U}f$ has more ...
- 508
3
votes
0
answers
108
views
How to know if a point lies inside a convex hull in n dimensions *efficiently*?
I want to calculate whether a point $P$ lies a convex hull or not in high dimensions, e.g. $n = 50$.
I am aware of the linear programming approach that boils down to solve the following equation for ...
- 31
0
votes
0
answers
41
views
on notation $\overline{\text{conv}}(A)$
Let $X$ a Banach space and $A \subset X$ a subset. I know the notation $\text{conv}(A)$ denotes the convex hull of $A$. What means the notation $\overline{\text{conv}}(A)$ used in comments in this ...
1
vote
0
answers
10
views
Bound the number of vertices on the convex hull of a self cartesian product
Given a finite set $A \subset \mathbb{R}$ with $n$ elements. One can construct a set $B$ in $\mathbb{R}^2$ using the cartesian product: $B = A \times A \subset \mathbb{R}^2$.
Is there any tight bound ...
- 1,223
1
vote
1
answer
66
views
What is the convex hull of this function?
Find the convex hull of this function:
y(x) = $\frac{1}{1+x^2} $
I'm attempting to understand the idea of a convex hull and attempted one of these problems. I'm a little confused because isn't the ...
- 349
0
votes
0
answers
57
views
Intersection of the convex hull of a compact set with a finite dimensional subspace
Let $H$ be a real Hilbert space, $K\subset H$ be a compact subset, $E\subset H$ be a finite dimensional linear subspace, then is the intersection $\mathrm{co}(K)\cap E$ closed in $E$? (Here $\mathrm{...
- 840
0
votes
1
answer
55
views
Geometric intuition behind affine hull
Let $S = \{x_1, x_2 \ldots x_n\}$ be a set of $n$ points in $\mathbb{R}^d$, then how can one geometrically interpret or visualise the affine hull of $S$?
It is somewhat straightforward to think about ...
- 351
2
votes
1
answer
99
views
Intersecting $B^d_\infty$ with the hyperplane $H = \{x\in \Bbb R^d: x_1 + \ldots + x_d = 0\}$
The following problem appears in Section $2.3$ (Exercise $13$) of these notes on Convex and Discrete Geometry (see Pg. $16$).
Consider the following vertices of $B_\infty^4 := \{x\in \Bbb R^4: \|x\|_\...
- 11.4k
0
votes
1
answer
47
views
Moving an interior point within a convex hull
Let $p_1,\dots,p_k,q\in\mathbb{R}^n$ such that $q$ is in the convex hull $\mathcal{C}$ of $p_1,\dots,p_k$. Let $q\ne q'\in\mathbb{R}^n$ be another point in $\mathcal{C}$. How do I show that there ...
- 480
0
votes
0
answers
77
views
Comparing n-dimensional convex hulls (non-square matrices)
I have the following problem. I have two convex hulls for the same data. One is the exact hull while the other uses an approximation algorithm to derive the hull. I now want to compare how good/bad ...
- 1
5
votes
2
answers
106
views
The convex hull of rotations does not contain reflections
$\newcommand{\SO}{\operatorname{SO}_n}$
$\newcommand{\Om}{\operatorname{O}_n^{-}}$
I saw here the following claim:
Let $\SO$ be the special orthogonal group, and let $\Om$ be the orthogonal matrices ...
- 24.4k
1
vote
1
answer
64
views
Finding the 2-facets of a convex 4D polytope (algorithm)
I'm an undergraduate student and I'm currently working on my end-of-degree-project. The main goal of this project is studying the $A_4$ root lattice, the geometry of its Voronoï complex, and using the ...
- 11
0
votes
1
answer
65
views
convex hull of the rational points of the unit sphere
What is the convex hull of the rational points of the unit sphere? Here, rational points are points whose coordinates are rational numbers.
Also, what is the convex hull of the irrational points of ...
- 524
0
votes
0
answers
31
views
What do you call Krein–Milman in 2D?
I've got a compact, convex subset $A$ of $\mathbb R^2$. I want to appeal to the fact that $A$ is the convex hull of its set of extreme points. In my case, $A$ is kind of an unfamiliar shape. I suspect ...
- 26.4k
0
votes
0
answers
26
views
Every closed convex cone is contained in a closed convex cone generated by a basis
Let $C$ be a closed convex cone in a Banach space $X$ such that $C\cap (-C)=\{0\}$. Is it true that there exists a Hamel basis $\mathscr{B}$ of $X$ such that
$$
C\subseteq \mathrm{cone}(\mathscr{B})\,\...
- 14.9k
2
votes
1
answer
186
views
Convex hull of open sets is an open set?
Let $(X,d)$ be a metric space. For all points $x,y \in X$ we define the metric segment between them as the following set:
$$\left [ x,y \right ] = \left \{ z \in X : d(x,z)+d(z,y)=d(x,y)\right \}$$
...
- 537
0
votes
0
answers
7
views
Is there any way to prove the following equation using Chernoff's Bound?
I was reading the paper 'Counting the Onion' by Ketan Dalal and came across this equation on page 161.enter image description here
The author has mentioned that it can be proven by Chernoff's Bound, ...
- 1
0
votes
1
answer
33
views
Clarification of the proof of the lemma 7.4 of the book Sets of Finite Perimeter and Geometric Variational Problems by Maggi.
I am reading the book "Sets of Finite Perimeter and Geometric Variational Problems: An Introduction to Geometric Measure Theory" by Francesco Maggi. In the chapter 7, called Lipschitz ...
- 185
1
vote
0
answers
59
views
Every $\mathcal{V}$-polyhedron is an $\mathcal{H}$-polyhedron
On page 32 of Ziegler's lectures, he wants to show that every $\mathcal{V}$-polyhedron is an $\mathcal{H}$-polyhedron. Ziegler defines the $\mathcal{V}$-polyhedron as the Minkowski sum of a convex ...
- 469
2
votes
0
answers
38
views
How to find a Convex Hull of a set defined by concave constraint?
I have a non-convex n-dimensional set defined by the constraints:
$$ \frac{n-2}{\sum_{i=1}^{n-1}\frac{1}{v_i}}<v_n $$
$$ 1<v_i<n-1.$$
I am trying to find a Convex Hull of this set. In the 3-...
- 165
1
vote
0
answers
58
views
Caratheodory's theorem original proof
I saw that Carathéodory's theorem was proved for the first time in this paper. My German is very poor and the paper seems to be about power series. My question is in which part of the paper does ...
- 5,563
0
votes
1
answer
70
views
Is the affine hull of a set equal to the affine hull of the convex hull of that set
Given a subset $S$ of $\mathbb{R}^n$, is it true that $\text{aff}(S) = \text{aff}(\text{co}(S))$? And if so how can I prove it rigidly?
- 307
2
votes
0
answers
39
views
Finding facets of a convex hull which are tangent to an enclosed ball, without using linear inequalities
This has been tormenting me for weeks. Given a set of $N$ points in $\mathbb{R}^d$, $N > d$, I want to find the largest ball enclosed within their convex hull, and I want to know which facets of ...
1
vote
0
answers
37
views
Show that the diagonal entries of a unitarily similar matrix are nonzero.
Let $A,B\in M_n$ be complex square matrices. Let $C=ABA^{-1}B^{-1}$ be the multiplicative commutator of $A, B$ and assume that both $A$ and $C$ are normal. Now assume that $AC=CA$ and $0\notin\...
- 2,071
3
votes
1
answer
85
views
If $\mu$ is a probability measure, then $\int_{X}\phi \ \mathrm{d}\mu\in\mathbb{C}$ lies in the closed convex hull of $\phi(X)\subset\mathbb{C}$
Let $\mu$ be a probability measure on a measurable space $X$. Suppose that $\phi\colon X\to\mathbb{C}$ is integrable with respect to $\mu$. How does one prove that $$\int_{X}\phi \ \mathrm{d}\mu\in\...
- 3,178
0
votes
0
answers
26
views
Theorem Bounding Minimum Supported Value Given An Expectation of a Discrete Random Variable
I have a discrete random variable $X$ and I know its expectation $\bar{X} = \mathbb{E}[X] \in \mathbb{R}$. I would like to say that the minimum of the support of $X$ must be $\leq \bar{X}$. Assuming ...
- 111