Questions tagged [convex-geometry]

A branch of geometry dealing with convex sets and functions. Polytopes, convex bodies, discrete geometry, linear programming, antimatroids, ...

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

Measurable sets of $\mathbb R^n$ forming unique absolutely continuous convex combinations?

If we consider a finite set $A\subset\mathbb R^n$, uniqueness of the convex decomposition of points in $A$ is equivalent to the absence of $\mu\neq0$ signed measure supported on $A$ such that $\mu(\...
user avatar
1 vote
0 answers
18 views

Adjacent vertices of a permutohedron which is the orbit of a point $x$ with repeated coordinates

Question: Let $x=(x_1, ..., x_n) \in \mathbb{R}^n$, and let $P$ be the convex hull of the points formed by permuting the coordinates of $x$. Given a vertex $y$ of $P$, what is a general rule for ...
user avatar
2 votes
0 answers
22 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
2 votes
1 answer
78 views

A neighborhood $Y$ of a set $X$ such that the line segment connecting any point in $Y$ and its projection to $X$ is contained in $Y$

A direct line from a point $p$ to a set $X$ is a line segment with one endpoint at $p$ and one endpoint in $X$, which is as short as any other line segment from $p$ to $X$. Given a closed set $X$ and ...
user avatar
1 vote
0 answers
28 views

Reference for a general theory of spaces of one-directional rays?

There is a lot of work done on projective spaces, over real, complex numbers or over an abstract field. But I do not find a reference for similar theory where the vectors are projected to the same &...
user avatar
2 votes
1 answer
87 views

Secondary polytope

Given a polytope $P$, what do the points of the secondary polytope correspond to? I know that the vertices of the secondary polytope correspond to regular triangulations of $P$. But what do the ...
user avatar
0 votes
0 answers
45 views

A sufficient condition for the decomposition of a bounded random vector

Given a matrix $A \in \mathbb{R}_{+}^{n\times m}$, where $n<m$ and rank($A$)=n. Define a set (a zonotope) $\mathcal{C}(A)=\{(x_1,x_2,\ldots,x_n)|\sum_{i=1}^m{\bf{a}}_ix_i,x_i \in [-1,1]\}$, where ${...
user avatar
0 votes
0 answers
36 views

Can a neural network with ReLU activation represents exactly all $B$-bounded and $L$-Lipschitz $K$-max-affine functions?

A max-affine function is defined as the maximum over a set of affine functions, which is always convex. More specifically, we define a $K$-max-affine function $f:\mathbb{R}^d\to\mathbb{R}$ that can be ...
user avatar
1 vote
0 answers
26 views

Support functions for subset and superset

I have an ellipse $\mathcal{E} = \{x^TAx = 1\}$, and I have a connected subset of an ellipse $U\subset \mathcal{E}$ For a given $\theta$ let $x_U^*(\theta) = \arg \sup\{\langle x,\theta\rangle, x\in ...
user avatar
  • 173
0 votes
0 answers
106 views

Approximation of zonoids

I have a question regarding the papers on approximating zonoids with zonotopes. I'll first write down the approximation problem and then state what my question is. Problem of Approximating Zonoids. ...
user avatar
  • 580
1 vote
0 answers
46 views

Is there any previous study on the relationship between convexity and the order of points in the general position?

Let's assume $V =(v_1,v_2,v_3,… ,v_n)$ is a set points in a general-position. For each point $v_i$, let's list the points in the order we encounter as we rotate around a certain direction (say ...
user avatar
  • 11
0 votes
0 answers
52 views

Sharp, salient and opposite cones

I have been reading about star shaped sets and support cones from this article. Can anyone please help me with examples the difference between a sharp and dull cone. How come a salient cone has a ...
user avatar
0 votes
0 answers
43 views

Regarding definition of convex cone and apex

I have been reading about star shaped sets and support cones from this article. I am wondering about the definition of the cone as to why is it defined this way? Why is it $C-a$? I am familiar with ...
user avatar
0 votes
0 answers
43 views

Examples of metric entropy of convex bodies in $\mathbb{R}^n$

I am interested in examples of convex bodies in $\mathbb{R}^n$ whose metric entropy in terms of the Euclidean norm has been characterized. Specifically if $N(K, \|\|_2, \varepsilon)$ denotes the ...
user avatar
2 votes
2 answers
97 views

Angle between a point in a convex polytope and the nearest point of a face

Let $P \subset \mathbb{R}^d$ be a convex polytope, and let $F$ be a face of $P$ (of co-dimension 1, let's say). Now let $x \in P \setminus F$ and let $y \in F$ be the nearest point of $F$ to $x$. Then ...
user avatar
  • 143
1 vote
1 answer
170 views

For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?

Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...
user avatar
  • 5,580
2 votes
2 answers
117 views

Distribution of the support function of convex bodies: beyond mean width

Let $K$ be a symmetric convex body in $\mathbb{R}^n$ (that is the unit ball of a norm). Let $h_K$ be its support function, that is $h_K(u) = \sup_{x \in K}\langle x,u \rangle$. The quantity $w(K) = \...
user avatar
  • 185
1 vote
0 answers
18 views

Optimal unions of planar convex regions

This post continues Optimal intersections between planar convex regions. Question: Given two planar convex polygonal regions $C_1$ and $C_2$, how does one algorithmically find how to place and orient ...
user avatar
  • 3,379
0 votes
0 answers
47 views

Diameter of inner parallel body

Let's say I have a convex polytope $\mathcal{P} \subset \mathbb{R}^n$ with non-empty interior. Let $\mathcal{P}=\bigcap_{i=1}^mH_i$ for some halfspaces $H_i$ and let $d=diam(\mathcal{P})=\sup\{\|x-y\|:...
user avatar
1 vote
0 answers
37 views

Comparing convex planar regions of equal perimeter and area - 2

We try to extend On comparing planar convex regions of equal perimeter and area . Given two planar convex regions C1 and C2 both with unit perimeter, we define the difference between C1 and C2 as the ...
user avatar
  • 3,379
5 votes
1 answer
182 views

Dimension reduction for non-negativity of elementary symmetric polynomials

Fix integers $1 \leq k \leq n$ and suppose $\mathbf{x} \in \mathbb{R}^n$ is such that $e_j(x_1,x_2,\ldots,x_n) \geq 0$ for all $1 \leq j \leq k$, where $e_j$ is the $j$-th elementary symmetric ...
user avatar
0 votes
1 answer
94 views

Estimation via projecting onto a convex body

Assume that $\theta$ is in a convex body $K \in \mathbb{R}^n$ and we observe $y = \theta + z$, where $z$ is a noise term (following, say, the normal distribution). Consider an estimator of $\theta$ by ...
user avatar
  • 623
1 vote
1 answer
59 views

Affine semigroup generating a lattice

This is a cross-post from MSE. Everything is assumed to be finite-dimensional. Let $S$ be a finitely generated affine semigroup (i.e. a subsemigroup of a lattice $N$ of a Euclidean space). Assume that ...
user avatar
0 votes
0 answers
49 views

Weak derivative of projection onto probabilist's simplex

Let $\Delta_n:=\{x\in [0,1]^n:\boldsymbol{1}^{\top}x=1\}$ denote the probabilist's $n$-simplex and let $P:\mathbb{R}^n\rightarrow\Delta_n$ denote the (Euclidean) metric projection onto this simplex ...
user avatar
2 votes
1 answer
101 views

Existence of preferred direction for a random vector with arbitrary distribution on sphere, under a condition on its covariance matrix

Let $X$ be random vector on the unit-sphere $S_{n-1}$ in $\mathbb R^n$. We don't assume that the distribution of $X$ is uniform on $S_{n-1}$ I'm interested in proving the existence of a (...
user avatar
  • 5,580
0 votes
0 answers
51 views

Projection onto a cone followed by a Schur-convex function

Let $Proj_C(x)$ denote the projection of a point $x$ onto a cone $C$. Let $f$ be a Schur-convex function. I'm considering $f(Proj_C(x))$ as a function of $x$. Are there any conditions on the cone $C$ ...
user avatar
  • 623
2 votes
0 answers
24 views

Monotonicity of perimeter of convex subsets of hyperbolic plane

I think that the perimeter of convex compact sets on the hyperbolic plane is monotone with respect to inclusion. I am looking for a reference to the above fact.
user avatar
  • 19k
1 vote
0 answers
64 views

Convex planar regions with optimal average 'centralness' and 'depth'

For a planar convex region $C$ and an interior point $P$ we define: the centralness ratio at $P$ is $$\min\left(\frac{\text{shorter portion of }\chi}{\text{longer portion of }\chi}:\chi\text{ is a ...
user avatar
  • 3,379
1 vote
1 answer
67 views

Sufficient conditions for the boundary unit-normal vector field of a closed convex set to be Lipschitz continuous

This is followup to the following question: On the Lipschitz continuity of the unit-normal vector field of a polytope Let $C$ be a (nonempty) closed convex subset of $\mathbb R^n$. Note that to every ...
user avatar
  • 5,580
2 votes
1 answer
99 views

On the Lipschitz continuity of $x \mapsto \arg\min_{c \in C}d(x,c)$ w.r.t Hausdorff distance

Let $C$ be a (nonempty) compact subset of euclidean $\mathbb R^n$, and consider the set-valued map $p_C:\mathbb R^n \to 2^C$ defined by $$ p_C(x) = \{c \in C \mid \|x-c\| = \mbox{dist}(x,C)\}, $$ ...
user avatar
  • 5,580
1 vote
1 answer
68 views

On the Lipschitz continuity of the unit-normal vector field of a polytope

Let $\mu$ be a probability measure on $\mathbb R^n$ and let $P$ be a compact polytope in $\mathbb R^n$. For any $x \in \mathbb R^n \setminus P$, let $p(x) \in P$ be (unique!) point in $P$ which is ...
user avatar
  • 5,580
2 votes
1 answer
102 views

Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points

Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$. Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that $$ \theta ...
user avatar
  • 5,580
1 vote
1 answer
50 views

Optimal number of half-spaces in H-representation of convex-hall of $n$ points in $\mathbb R^d$

Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
user avatar
  • 5,580
7 votes
4 answers
379 views

What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?

Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by $...
user avatar
  • 5,580
0 votes
0 answers
64 views

On finding optimal convex planar shapes to cover a given convex planar shape

Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
user avatar
  • 3,379
1 vote
0 answers
141 views

Is there a polynomial expression for the volume of the following set?

Denote the unit $\ell_2$ ball in $\mathbb{R}^n$ as $\mathcal{B}_n$. It is widely kown that for a convex body $\mathcal{K}\subseteq \mathbb{R}^n$, the $n$-dimensional volume of the parallel body $\...
user avatar
  • 532
9 votes
2 answers
338 views

Which convex bodies roll straight?

Let $K$ be a convex body in $\mathbb{R}^3$. Suppose $K$ is held at some position and orientation on an inclined plane, and released. Let there be sufficient friction so that it rolls without slippage. ...
user avatar
3 votes
1 answer
180 views

Well-behaved trajectories

Call trajectory any continuous function $f: \mathbb{R}_{\geq 0} \to \mathbb{R}^n$ (here, $\mathbb{R}_{\geq 0}$ is interpreted as time). A polyhedral partition of $\mathbb{R}^n$ is a finite set of ...
user avatar
  • 141
6 votes
2 answers
210 views

RELU representation of $\max(x,y,z)$

Here is a question that occurred to me while learning about neural networks. For $t\in\mathbb{R}$ put $t_+=\max(0,t)$, so $t_+=t$ if $t\geq 0$ and $t_+=0$ if $t\leq 0$. (This is RELU=rectified linear ...
user avatar
1 vote
1 answer
64 views

How to compute external angles of a hypersimplex?

Recently, I concern with the volume of the outer parallel body of a hypersimplex that is defined as follows $$ \mathcal{H}_s(n,k)=\left\{ (x_1,\cdots,x_n):\sum_{i=1}^n x_i=k,x_i\in[0,1] \right\}, $$ ...
user avatar
  • 532
3 votes
0 answers
85 views

Hausdorff measure of the unit ball of a norm on $\mathbb{R}^n$ is a universal constant

In [1], Kirchheim proved the area formula for Lipschitz maps $f\colon \mathbb{R}^n\to X$ where $X$ is an arbitrary metric space, using the notion of metric differentiability. The metric derivative of $...
user avatar
4 votes
0 answers
43 views

On ways to measure the difference between two planar convex regions

This earlier post attempted to quantify the difference between a pair of planar convex regions of equal area and perimeter using Hausdorff distance: On comparing planar convex regions of equal ...
user avatar
  • 3,379
1 vote
1 answer
57 views

Lower-bound for $\mathbb E[e^{-b(v^\top X - c)^2}]$, when $X$ is log-concave in high-dimensions

Let $d$ be a large positive integer. Fix a unit-vector $v \in \mathbb R^d$, and scalars $b,c \in \mathbb R$ with $b > 0$. Let $X$ be a log-concave random vector in $\mathbb R^d$ normalized so that ...
user avatar
  • 5,580
6 votes
1 answer
117 views

Isometric imbedding of a 2-disk into Euclidean 3-space

Let us call a cap the intersection of the boundary of 3-dimensional convex compact set $K$ in $\mathbb{R}^3$ with a half-space bounded by a plane $H$ such that the orthogonal projection to $H$ of this ...
user avatar
  • 19k
3 votes
1 answer
86 views

Is a cap an Alexandrov space?

Let us call a cap the intersection of the boundary of 3-dimensional convex compact set $K$ in $\mathbb{R}^3$ with a half-space bounded by a plane $H$ such that the orthogonal projection to $H$ of this ...
user avatar
  • 19k
6 votes
3 answers
378 views

Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace

Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
user avatar
  • 5,580
3 votes
1 answer
102 views

Finding the smallest centrally symmetric region that contains a convex planar region

Given a convex polygonal region C, how does one find/characterize the smallest zonogon (centrally symmetric convex polygon https://en.wikipedia.org/wiki/Zonogon) that contains C? Note 1: In question ...
user avatar
  • 3,379
1 vote
0 answers
37 views

Minimum bounding rectangle of symmetric convex bodies in the plane : is the ball the worst case

The minimal rectangle containing the euclidean ball in the plane is the standard cube $B_\infty = [-1;1]^2$. I would like to know if the euclidean ball is the worst symmetric convex body to be ...
user avatar
  • 185
2 votes
0 answers
59 views

Separation of convexity on uniquely geodesic space

A metric $d: X \times X \to [0,\infty)$ is said to be intrinsic provided that the distance between any two points is the infimum of the lengths of paths joining the points. A space is an inner metric ...
user avatar
  • 783
1 vote
0 answers
66 views

A ratio to measure 'roundedness' of planar convex regions

Ref: A center of convex planar regions based on chords The above discussion quotes the definition of 'centralness coefficient' and defines a center of a planar convex region. 1/2 is the least possible ...
user avatar
  • 3,379

1
2 3 4 5
18