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

learn more… | top users | synonyms

4
votes
4answers
12k views

How to find overlap between two convex hulls, along with the overlap area

I have two boundaries of two planar polygons, say, B1 and B2 of polygons P1 and P2 (with m and n points in Boundaries B1 and B2). I want to find out if the polygons overlap or not. If they overlap, ...
5
votes
2answers
251 views

Diameter-area ratio for affine tranformations.

Consider an convex plane figure $F$. How to prove that there is an affine transformation $a$ such that $\sqrt{3}$ diameter$(a(F))^2\leq 4$ area$(a(F))$? I found only one reference, to "Über einige ...
0
votes
2answers
269 views

Higher dimensional convex hull

Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as ...
2
votes
1answer
591 views

non-convex Polytope definition

I have a simple question. I read that given a vector space $N_{\mathbb{R}}$ over $\mathbb{R}$, we can define a convex polytope in the following way: $$P:= \Big\{ \sum_{u\in S} \mu_u u \,\Big| \, ...
3
votes
2answers
406 views

Intersection points of straight line segment with Voronoi diagram

Hi, I need to find the x,y points of intersection of a vertical line with the edges of the Voronoi cells it goes through in a defined, rectangular plane region with a given Voronoi tesselation. Is ...
5
votes
1answer
403 views

A question on the Mahler conjecture

In its asymmetric version, the Mahler conjecture states that if $K \subset \mathbb{R^n}$ is a convex body containing the origin as an interior point and $$ K^* := \{y \in \mathbb{R}^n : \langle y, x ...
1
vote
2answers
278 views

Volume of a convex set

Say $K$ is a $n$-dimensional convex subset of $\mathbb R^n$ around the origin. Say we know $Vol_{n - 1}(\pi_{\theta^{\bot}}) K)$ where $\theta^\bot$ is the linear subspace of $\mathbb{R}^n$ orthogonal ...
3
votes
0answers
113 views

Covering points with a convex hull

Consider a set of $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$, for some $n \gg d$. Suppose $\{x_1,\ldots,x_n\} \subset C \subset \mathbb{R}^d$. Say that a set of points $y_1,\ldots,y_m \in C$ covers ...
2
votes
1answer
498 views

Surface area of a convex set

In 2D perimeter(P) of a convex set around origin may be written as $P=1/2 \int m(\theta) d\theta$. Where $m(\theta)$ is the diameter of the set in the $\theta$ direction. This is related to ...
0
votes
1answer
196 views

Extensions of Carathéodory's theorem

We know about the Carathéodory's theorem which is on the convex bodies of $\mathbb{R}^d$. My question is, how far we can extend it? Is it true for say, any convex object of Banach space, or for convex ...
6
votes
1answer
275 views

Monotonicity of Loewner ellipsoid?

Given two $0$-symmetric convex bodies $K \subset L \subset \mathbb{R}^n$, is it true that the Loewner ellipsoid of $K$ is contained in the Loewner ellipsoid of $L$? I have just finished proving a ...
2
votes
1answer
102 views

Maximal cross sections of the Cartesian product of two planar domains

Let $K$ and $L$ be two two-dimensional convex bodies, and consider their Cartesian product $K\times L\subseteq \mathbb R^4$. Now let $U_\theta\subseteq \mathbb R^4$ be the two-dimensional subspace ...
4
votes
1answer
257 views

A question of compactness in the geometry of numbers

Given a star body $S \subset \mathbb{R}^n$ with the origin as interior point, the critical determinant of $S$---usually denoted as $\Delta(S)$---is the infimum of the determinants of all lattices ...
2
votes
0answers
44 views

Conditions under which a set of points have a low weight representation under some basis

Let $S \subset R^d$ be a convex polytope in $d$ dimensional real space. Say that $S$ has weight $w$ if there exists some basis $x_1,\ldots,x_d$ such that for every point $v \in S$, we can write $v = ...
2
votes
2answers
182 views

What is the dual of an semidefinitely representable (SDR) cone?

The Question Let $V\simeq \mathbb{R}^r$ be an $r$-dimensional vector space with the usual Euclidean inner product. Let $\mathcal K\subset V$ be a cone defined as $$ \mathcal K=\Big\{x\in V\ ...
4
votes
2answers
428 views

the perimeter of a non-convex set

Let $\Omega$ be an open, bounded set in $\mathbb{R}^n$ with $C^1$ boundary. Is it true that the perimeter of the convex hull of $\Omega$ is smaller or equal the perimeter of $\Omega$ with equality if ...
4
votes
2answers
497 views

Expected distance of a random point to the convex hull of N other points

Let $X_1, \cdots, X_N$ be i.i.d. $d$-dimensional random vectors, the exact distribution of $X$ is not very important in my application (as long as it continuous) so pick the one that works best, but ...
12
votes
0answers
218 views

Does there always exist a self dual polytope that contains a given polytope contained in its dual?

Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...
2
votes
1answer
254 views

another diameter-perimeter-area inequality

Recently I learnt that $$ \inf\frac{diam(C)(per(C)-2diam(C))}{area(C)}=0$$ where the infimum is taken over all plane convex bodies $C$ (say, with non-zero area). In other words, there is no ...
3
votes
2answers
308 views

a diameter-perimeter-area inequality for convex figures

Is the following inequality known? I believe it's true, but I could find no reference. For any convex body $C$ in the plane we have $$\left(4-\frac{8}{\pi}\right)area(C)\leq > ...
22
votes
3answers
2k views

Research trends in geometry of numbers?

Geometry of numbers was initiated by Hermann Minkowski roughly a hundred years ago. At its heart is the relation between lattices (the group, not the poset) and convex bodies. One of its fundamental ...
2
votes
1answer
308 views

A quantitative version of Straszewicz's theorem?

Let $C$ be a compact convex subset of Euclidean space. Recall that $x\in C$ is an exposed point of $C$ if there is a plane $P$ such that $P\cap C = \{x\}$. It is obvious that exposed points are ...
4
votes
0answers
175 views

Convex bodies with symmetric shadows.

Theorem. If all orthogonal projections of a convex body $K \subset \mathbb{R}^n$ onto $2$-dimensional subspaces have a center of symmetry, then $K$ has a center of symmetry. This is a classic result ...
8
votes
0answers
343 views

Volume-like property to upper bound lattice points in a convex body

The following question arises in passing in a joint paper that I am working on. Let $K$ be a centrally symmetric convex body in an $n$-dimensional real vector space $V$ which contains a lattice $L$. ...
4
votes
1answer
463 views

An elementary probability question

Let $X$ be a $d$-dimensional random vector distributed according to probability measure $D$. At least the second moment of the coordinates of $X$ is finite. Consider $n+1$ samples $X_0, \ldots, X_n ...
7
votes
0answers
221 views

From convex geometry to contact topology

Here is a problem in contact topology that was suggested by Petya's answer to this mathoverflow question of mine. Let $S^* \mathbb{R}^n$ be the space of cooriented contact elements of $\mathbb{R}^n$. ...
12
votes
2answers
483 views

A problem on convex geometry

Consider a convex body $K \subset \mathbb{R}^n$ containing the origin in its interior. Although the body is not necessarily symmetric, let us say that two points in its boundary $\partial K$ are ...
10
votes
2answers
275 views

Can you see smoothness of the boundary of a convex body from its shadow?

Let $d \geq 3$ and suppose that $K \subset \mathbb{R}^{d}$ is a convex body (compact, convex, non-empty interior). Is the following true? The boundary $\partial K$ is a $C^1$-manifold if and only ...
0
votes
2answers
523 views

Nonzero convex combinations of convex hull vertices to yield an inner point

Two questions: 1) (ALREADY ANSWERED) This is likely to be a very basic question for you folks. Carathéodory's theorem gives us an upper bound for the minimum number of convex hull vertices that can ...
7
votes
0answers
128 views

Almost Isodiametric Sets

Hi, The isodiametric inequality tells us that, of all sets of diameter $r$, the one with the largest Lebesgue measure is the ball of radius $r/2$ - and this holds regardless of norm. Let $\tau(r)$ be ...
0
votes
1answer
598 views

Is minimum of convex envelope the same as minimum of the original function?

Hello everyone my question is: $Question:$ Consider a function $f:X \rightarrow \mathbf R$ where $X$ is a convex subset of $\mathbf{R}^n$. The convex envelope of $f$ over $X$ is defined as the ...
7
votes
2answers
275 views

Duality between extremal points and extremal maps

Suppose I have a convex set $C\subset\mathbb{R}^n$ such that $0\in C$ and every Cauchy sequence in $C$ converges in $C$, but $C$ need not be bounded. (Actually I want unbounded $C$). Consider the set ...
21
votes
4answers
742 views

Do random projections (approximately) preserve convexity?

The Johnson-Lindenstrauss lemma implies that any set of $k$ points in $\mathbb{R}^d$ can be randomly projected into $d' \approx \log(k)/\epsilon^2$ dimensions such that the distances between each pair ...
11
votes
1answer
345 views

Detecting a hidden convex body with line probes

Imagine that, somewhere inside an origin-centered, unit-radius sphere $S$ in $\mathbb{R}^3$, sits a convex body $K$ of volume vol$(K)=\alpha (\frac{4}{3} \pi)$, with $\alpha < 1$ the fraction of ...
5
votes
5answers
679 views

Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

A friend asked me to post the following question. He's not an MO user and felt it would be better received if asked by someone who was already known to the community. This is not my area, but I'll do ...
5
votes
0answers
200 views

Generalization of the non-existence of a monostatic planar body

Domokos, Papadopulos, and Ruina showed that there does not exist a convex planar rigid body of uniform density which has only one orientation of stable equilibrium and one orientation of unstable ...
3
votes
2answers
485 views

The (Sigma) Algebra of Convex Sets

This is a question-by-proxy for a colleague from computer science. I'm sure many people here are already aware that convex decomposition forms an important sub-field of both computational geometry and ...
0
votes
0answers
180 views

A linear program related question

Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice. Let $\alpha^k \in (\alpha_1^k, ...
6
votes
1answer
358 views

When is the hull of a space curve composed of developable patches?

Let $C$ be a smooth curve in $\mathbb{R}^3$ that lies entirely on its convex hull, $\cal{H}(C)$. Under what conditions on $C$ is $\cal{H}(C)$ the union of developable surface patches? I believe ...
2
votes
1answer
143 views

coarser than triangulations “almost partitions” into simplices

The total space $T$ of an embedded into $\mathbb{R}^n$ pure $n$-dimensional simplicial complex (in other words, the union of finitely many $n$-dimensional compact convex polytopes) sometimes admits an ...
2
votes
0answers
74 views

Affine endomaps and isometries of convex bodies

Let $B$ stand for a compact convex body in a Hilbert space $H$. Suppose that a finite group $G=\{g_1,\ldots,g_n\}$ acts, via affine maps, on $B$. Write $B'$ for the image of $B$ in $B^n$ by the ...
4
votes
0answers
135 views

Convexified threshold of a function

Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set. It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when ...
1
vote
1answer
976 views

proving the interior of a dual cone is the set of vectors whose inner product is strictly positive on the cone

Apologies for posting such a simple question to mathoverflow. I've have been stuck trying to solve this problem for some time and have posted this same query to math.stackexchange (but have received ...
4
votes
0answers
241 views

Smoothness of the convolution of a singular measure with itself

Let $\gamma:I\subset\mathbb{R}\rightarrow\mathbb{R}^2, s\mapsto \gamma(s)$, denote the arclength parametrization of a smooth, convex curve $\Gamma:=\gamma(I)\subset\mathbb{R}^2$. Equip $\Gamma$ with ...
2
votes
0answers
233 views

Convexity and probability

Problem instance: A closed convex body $B\subset {\Bbb R}^n$ of volume 1; a point $p\in B$; and a real number $v\in(0,1)$. Objective: Find the probability $P(B,v,p)$ that $p\in B'$, for $B'$ a ...
2
votes
1answer
351 views

Quermassintegrals as mean curvature integrals

It is well-known that the quermassintegrals $W_{i}$ of a convex body $K\subset \mathbb{R}^{n}$ can be written as a mean curvature integral $$ W_{i}(K)=n^{-1}\int_{\partial K}H_{i-1} ...
11
votes
3answers
557 views

finding the most-isolated point in a high-dimensional cube

I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find $\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} ...
3
votes
3answers
664 views

How to find the minimum number of hyperplanes to define a convex hull?

I have the following problem: I have a convex hull $\Omega$ defined by a set of n-dimensional hyperplanes $S = [(n_1,d_1), (n_2,d_2),...,(n_k,d_k)]$ such that a point $p \in \Omega$ if $n_i^T p \geq ...
7
votes
2answers
323 views

Continuity of barycentre in Hausdorff metric

Let $K_1$, $K_2$ be two convex compact sets in $\mathbb{R}^d$, and $p_1,p_2$ be their barycenters. Is it true that the distance between $p_1$ and $p_2$ does not exceed a Hausdorff distance between ...
2
votes
2answers
429 views

Finite imensional subspaces of $L^\infty.$

This is the question I had meant to ask when I asked this question.: Is there a concise characterization of finite dimensional subspaces of $L^\infty?$ (that's what the discussion with @fedja was ...