Skip to main content

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
4 votes
0 answers
105 views

When does $A-B= B-A$ hold for bounded, closed, convex sets $A,B$?

When does $A-B=B-A$ hold for bounded, closed, convex sets $A,B\subset \mathbb{R}^n$? In 1D it is easy to see that this holds true if and only if the two intervals have the same center points. Is ...
Thorsten Hohage's user avatar
1 vote
2 answers
60 views

Simple proof that John's theorem is sharp?

We denote $B^n_p \subset \mathbb{R}^n$ the unit ball $\{\|x\|_p \leq 1\} \subset \mathbb{R}^n$, $p \in [1, \infty]$. Let $\mathcal{K}^n$ denote the class of symmetric convex bodies in $\mathbb{R}^n$. ...
Drew Brady's user avatar
  • 3,774
-2 votes
0 answers
19 views

Does the set where a convex function fails to be second derivative have some geometric properties? [closed]

I know it is of Hausdorff measure 0 by Alexsandrov's theorem. And the second derivative of a convex function can be viewed as a Radon measure. Does it have some other geometic properties?
ccs's user avatar
  • 1
0 votes
0 answers
8 views

Is a concave parametric curve along a concave surface guaranteed to be concave along another concave surface?

Take a parametrized probability distribution $\mathbf{p}(\theta)=( p_0(\theta),p_1(\theta),\cdots p_n(\theta))$ and two permutation-symmetric, everywhere-concave functions $S_1(\mathbf{p})$ and $S_2(\...
Quantum Mechanic's user avatar
1 vote
4 answers
102 views

Find the coordinates of the closest point on the surface of the ellipsoid to the line in space

I have an equation for an ellipsoid and a parametric equation for a line in space. The equation for an ellipsoid is in the general form: $$x^2/a_1^2 + y^2/a_2^2+z^2/a_3^2 = 1$$ The parametric equation ...
zymaster's user avatar
4 votes
0 answers
204 views

An arrangements of the hyperplanes.

Consider a finite set L of lines in the plane. They divide the plane into convex subsets of various dimensions, as is indicated in the following picture with 4 lines: The intersections of the lines, ...
D. S.'s user avatar
  • 282
2 votes
1 answer
66 views

Number of cells in simple arrangement

Consider a finite set L of lines in the plane. They divide the plane into convex subsets of various dimensions, as is indicated in the following picture with 4 lines: The intersections of the lines, ...
D. S.'s user avatar
  • 282
2 votes
0 answers
27 views

Gauss map is a diffeomorphism

Consider a smooth, convex function $f:\Bbb{R}^n\to \Bbb{R}$ such that the open subset $U=f^{-1}(-\infty, 0)$ has a smooth boundary $\partial U=f^{-1}(0)$. Consider the following smooth map $g: \...
dsjkhbjdskfhkjh jhdj's user avatar
0 votes
1 answer
48 views

Understanding the Separation theorem

Separation theorem: Let $P, Q⊆\mathbb{R}^d$ be disjoint compact convex sets. Then there exist $v∈ \mathbb{R}^d$ and $c_1, c_2∈\mathbb{R}$ with $c_1<c_2$ such that $x.v≤c_1$ for every $x∈P$ $x.v≥...
D. S.'s user avatar
  • 282
0 votes
1 answer
80 views

Helly's theorem for $n=d+1$ [closed]

Helly's theorem : Let $C_1,\ldots,C_n$, $n\geq d+1$, be convex sets in $\Bbb R^d$. Suppose every $d+1$ have a common intersection. Then they all have a common intersection. I can find the proofs for $...
A. H.'s user avatar
  • 72
0 votes
1 answer
25 views

Normal Cones on a Circular Arc

Let $C = \{(x, y) \in \mathbb{R}^2: x^2 + y^2 \leq 1, y \geq 0, y \leq x\}.$ I wish to determine the normal cone $N_C(x_0, y_0)$, for any $(x_0, y_0)$ on the boundary of $C$. There are six cases to ...
V. Elizabeth's user avatar
2 votes
0 answers
57 views

Covariances not below $\Sigma$

$\Sigma_0,\Sigma_1,\dots,\Sigma_K$ are real covariance matrices. I’m interested in the set of matrices $$\bigcap_{k=1}^K \left\{x: 0 \preceq x \preceq \Sigma_0, \ x\not\prec\Sigma_k\right\}.$$ I’m ...
Christian Chapman's user avatar
0 votes
1 answer
46 views

Every point inside a convex polyhedron can be expressed as a convex combination of the vertices.

Consider a polyhedron $P$ in $\mathbb R^n$. That is, $P$ is an intersection of linear inequalities and linear equations (in general, an intersection of linear inequalities) ; $$P = \{x\in\mathbb R^n:...
govindah's user avatar
  • 174
1 vote
0 answers
23 views

Is there a standard name for a convex set whose (algebraic) relative interior is non-empty?

I am writing a document in which I will have to use extensively convex sets whose (algebraic) relative interiors are non-empty. I am wondering if there is a standard name for such sets, the name that ...
P. Quinton's user avatar
  • 6,076
0 votes
0 answers
21 views

Continuity of distance to a convex set along a particular direction

Consider a compact, convex set $X \subseteq R^n$. Let $e = (1, 0, \dots, 0)\in R^n$ be a unit vector along a particular direction. Define a function $d: X \rightarrow R$ given by $d(x) = \max\{\alpha \...
ashtavakra's user avatar
2 votes
1 answer
93 views

Convexity structures and partial orders

Can any convexity structure be defined by a partial order $\preceq$ in the sense of the order topology: a given set $A$ is convex if for any $a,b \in A$ and any other element $c$ for which $a\preceq c ...
user146125's user avatar
14 votes
0 answers
150 views
+50

8000 congruent convex asteroids can form a "stable cluster". How much better can we do?

The Infinite Case The "Trapped in Thickland" puzzle in Peter Winkler's latest edition of Mathematical Puzzles asks the following (in my own words): The Infinite Asteroid Belt is a region in ...
greenturtle3141's user avatar
1 vote
0 answers
32 views

Slack Variables and Duality in Convex Optimization

In context of convex optimization the slack variable $\vec{s} \ge 0$ can be used to convert inequality $A \vec{x} \le \vec{b}$ to the equality $A \vec{x} + \vec{s}= \vec{b}$. Now in wikipedia is ...
user267839's user avatar
  • 7,589
0 votes
0 answers
27 views

Can Cauchy's polyhedron rigidity theorem be generalized to affine transformations?

Conjecture: Suppose $f$ and $g$ are two convex realizations of an abstract polyhedron $P$. (In other words, $f(P)$ and $g(P)$ are two convex polyhedra whose face lattices are isomorphic.) Also suppose,...
mr_e_man's user avatar
  • 5,726
0 votes
1 answer
28 views

a question about cluster points of a convex set

Suppose $X$ is a nonempty convex subset of $R^n$, $x$ is a cluster point of $X$ and $y$ is a boundary of $X$. Is there a sequence $\{x_n\}$ converging to $x$ ($y$) such that for all $n, x_n \notin ...
Aimin Xu's user avatar
  • 491
3 votes
1 answer
46 views

Can you find a linear system with these integer solutions?

I have this expression $(x \geq 1) \vee(x=0 \,\wedge\, y -z \geq 1)$ which I am solving over the nonnegative integers $x,y,z \in \mathbb{Z}_0^+$. I suspect it is impossible to find a system of linear ...
user326210's user avatar
  • 17.7k
0 votes
0 answers
42 views

Is the feasible region for convex combinations of powers of $N$ cosines independent of $N$?

Let $x = \sum_{i=1}^N a_i \cos^2(\theta_i)$ and $y = \sum_{i=1}^N a_i \cos^3(\theta_i)$ be the two convex combinations of powers of cosines, where the variables satisfy the following constraints (1). $...
Luzveraz's user avatar
7 votes
0 answers
126 views

Number of unit cubes meeting the boundary of a convex set

Suppose $C \subseteq [0,n)^k$ is a convex set, and $\partial C$ is its topological boundary: its closure minus its interior. Is it true that $\partial C$ meets at most $2kn^{k-1}$ unit cubes in [0,n)^...
Andrew Marks's user avatar
2 votes
1 answer
32 views

Dialation of a convex set covers its mirror

Problem: Let $C\subset \mathbb{R}^d$ be a compact convex set. Prove that the mirror image of $C$ can be covered by a suitable translate of $C$ blown up by the factor of $d$; that is, there is an $x \...
agent_cracker103's user avatar
0 votes
0 answers
29 views

How to prove that when applying the separating axis theorem to convex 3D polyhedra, I only need to consider the face and edge-edge normals

So when checking to see if two convex 3D polyhedra are colliding, it is known that you only have to consider separation along the outward face normals and the normals obtained by crossing the edges of ...
Minecraft dirt block's user avatar
1 vote
1 answer
29 views

Algorithm to find if intersection of convex sets is empty [closed]

Is there an algorithm to find if the intersection of two convex sets is empty or not. The projection onto convex method (POCS) and similar methods finds a point in the intersection, but will they ...
user221985's user avatar
0 votes
1 answer
10 views

Maximal bound for area of set-difference of circular disc and arbitrary convex figure, given longest cord length of such difference set.

Given circular disc $A$, which intersects with arbitrary convex figure $B$, denote difference of these two sets as $C: C = A – B$. Denote length of the longest interval, which belongs entirely to $C$ (...
Vladimir_U's user avatar
0 votes
1 answer
59 views

Convex function $f(x,y) = \lvert xy \rvert + a (x^2 + y^2)$

Show that the function $f(x,y) = \lvert xy \rvert + a (x^2 + y^2)$ is convex if and only if $a \ge 1/2$. $f$ is not differentiable, right? If we did not have the absolute value we could differentiate ...
vassilisP's user avatar
2 votes
0 answers
49 views

Do we have better bounds than $n^{-n}$ on the maximum ellipsoid in a unit-volume convex body in $\mathbb{R}^n$?

By a theorem of Fritz John, we know that a compact convex body $K\subset\mathbb{R}^n$ of nonempty interior contains a unique maximal ellipsoid $E$, sometimes called the John ellipsoid, such that $E\...
RavenclawPrefect's user avatar
1 vote
1 answer
63 views

Algorithms to Find Convex Combination Coefficients for a Point within a Convex Polytope Without Explicit Representation

Set Up: Let $P$ be a finite convex polytope. Assume that we do not have a representation for $P$ (like a V-, H- or Z-representation of $P$), all we have is an algorithm which can find a point of $P$ ...
Josstopher's user avatar
0 votes
0 answers
17 views

Integral of log-concave function on the boundaries of convex sets

Let $g$ be a convex function on $\mathbb{R}^d$ and $B_1 \subset B_2 \subset \mathbb{R}^d$ be two convex sets with smooth boundaries $\partial B_1, \partial B_2$. Then do we always have the following ...
HenryYRZ's user avatar
0 votes
1 answer
22 views

Name of $d$-simplex with "orthogonal" complementary subsimplices

Three-dimensional space allows for the following sequence of tetrahedra: The regular tetrahedron with $d+1$ vertices The pyramid whose base is a triangle with $d$ vertices centered at $0$ in $\{x_3=0\...
AlpinistKitten's user avatar
0 votes
1 answer
30 views

Closure of projecting cone is the tangent cone

Let $Y \subseteq \mathbb{R}^n$ be a convex set and let $\bar{y} \in Y$. The tangent cone to $Y$ at $\bar{y}$, denoted $T(Y, \bar{y})$, is the set of all limits of the form $h = \lim t_{l}(y_{l} - \bar{...
AMfrn's user avatar
  • 35
1 vote
1 answer
18 views

Is it always possible to cross two opposite pairs of adjacent sides of a convex 2n-gon by two parallel lines, not crossing through vertex?

We are given a convex polygon with even number of vertexes ($ABCDEF$ in my picture). We want to prove that it is always possible to find two pairs of adjacent sides that have the same amount of ...
Vladimir_U's user avatar
0 votes
0 answers
11 views

Charecterization of normal equivalence (convex polytopes).

Call two convex polytopes (in $\mathbb{R}^n$) normally equivalent if their normal fans coincide. For example it is immediate that if $P$ is a polytope then $\lambda P + x$ is normally equivalent for $\...
201p's user avatar
  • 797
0 votes
1 answer
59 views

How to recognize affinely dependent or independent?

I have been trying to understand example of affinely dependent (AD) or affinely independent(AI). But from the above images how are leftmost two figures AI and is rightmost AD? I am not able to ...
user avatar
0 votes
3 answers
81 views

Why affinely independent points in $\mathbb{R^d}$ is $d+1$?

Below text quoted from Jiff Matousek book: Affine dependence of $a_1 ,\dots, a_n$ is equivalent to linear dependence of the $n-1$ vectors $a_1 - a_n, a_2 - a_n, \dots, a_{n-1}-a_n$ . Therefore, ...
user avatar
0 votes
0 answers
10 views

What does the smallest possible pairing between a convex set and its polar measure?

Assume that $C\subset\mathbb{R}^n$ is a compact, convex set with $0\in \mathrm{int}(C)$. We define the polar set as $$ C^\ast := \{\, y\in\mathbb{R}^n \, \mid \, \, \langle x , y\rangle \leq 1 \, \...
Levent's user avatar
  • 4,852
4 votes
1 answer
73 views

If $A$ has strictly positive reach, does the set $\{ x \in A \colon B(x,\epsilon) \subseteq A \}$ also?

Let $A \subseteq \mathbb{R}^n$ with $\text{reach}(A) > 0$ (see https://en.wikipedia.org/wiki/Reach_(mathematics) ). Define for any $\epsilon>0$, the "removal of $\epsilon$-thick boundary&...
Jacobiman's user avatar
  • 1,023
0 votes
0 answers
24 views

Polar Set of a Polyhedra is a Polytope

I am having trouble to verify Proposition 2 from the following MIT OCW document: Is there a way for us to see the equivalence of $C_1$ and $C_2$ simply through the definition? I do notice there was a ...
Partial T's user avatar
  • 593
0 votes
1 answer
31 views

Constrained Optimizer as Projection of Unconstrained Optimizer

Let $f:H\to \mathbb{R}$ be a once Fréchet differentiable strictly convex function on a separable Hilbert space and $C$ be a non-empty closed and convex body therein. Let $P_C:H\to C$ denote the ...
ABIM's user avatar
  • 6,779
1 vote
0 answers
23 views

Relationship between the boundaries of two convex sets

Let $S\subset\mathbb{R}^3$ be a closed convex set contained in a plane $H$. (The plane $H$ passes through the point $\mathbf{0}$ and is orthogonal to the unit vector $\hat{\mathcal{r}}\in \mathbb{R}^...
Gino's user avatar
  • 372
1 vote
0 answers
31 views

Categories internal to the category of convex sets

Let $\text{Conv}$ be the category of convex sets, as described by Proposition 1 of Jacobs. I want to understand the nature of categories internal to Conv. Any concrete description would be useful, but ...
Richard Southwell's user avatar
0 votes
1 answer
48 views

A question about compactness and polytopes

I saw a statement as follow: Let $A$ be a compact set in $\mathbb{R}^n$, and $P\subset A$ a closed subset of $A$. By compactness, to prove that $P$ is a polytope, it sufffices to work locally about a ...
Hobo's user avatar
  • 327
0 votes
0 answers
17 views

3-dimensional convex polytope with adjacent vertices is a 3-simlpex

Let $P=\rm{conv} ( \textit{V} )$ be an convex $3$-dimensional polytope with vertices $V$ in which every two vertices $x,y \in V$ are adjacent. Show that $P$ is a $3$-Simplex. I think we can use radon'...
Lukas's user avatar
  • 141
1 vote
1 answer
58 views

Is the constraint $f(A) = \sqrt{x^T A x} \le t$ convex

I know that second order cone constraint $ f(x) = \sqrt{x^TAx}\le t $ is convex set given matrix $A$ semi-definite (If I am wrong, please point it out.) I wonder if the variable changes from vextor $x$...
Kaiming Zhang's user avatar
0 votes
1 answer
20 views

How can I show in a formal way this solution of Bezdek-Connelly Theorem?

Question Show that for $n=4$, the Bezdek-Connelly theorem is tight: there exists 4 unit circles in the plane such that every two circles intersect at exactly two points, and there are exactly 4 ...
Mr Prof's user avatar
  • 451
-1 votes
1 answer
35 views

Is there any Example of 8 Points in the Plane that Determine only 4 Ordinary Lines (Gallai Lines)?

I want to find an example of 8 points in the plane that determine only 4 ordinary lines (lines containing exactly 2 points). I have tried all the shapes I know, but I can’t seem to come up with an ...
Mr Prof's user avatar
  • 451
0 votes
0 answers
33 views

How Should I Prove there are at least Two Configurations for $9_3$?

Question Prove that there are at least two different geometric ($9_3$) configurations. To prove that two configurations are different, show that they are different as combinatorial configurations. ...
Mr Prof's user avatar
  • 451
0 votes
1 answer
27 views

How to show infx∈D⟨p,x⟩>supy∈Ω⟨p,y⟩?

Suppose thet $\Omega \subset \mathbb R^n$ is closed convex, and $ D \subset \mathbb R^n$ is compact convex. If $\Omega \cap D = \varnothing$, then please show$\exists p \in \mathbb R^n$ with $inf_{x \...
Harry's user avatar
  • 23

1
2 3 4 5
30