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
86 votes
2 answers
6k views

Light reflecting off Christmas-tree balls

...
Joseph O'Rourke's user avatar
68 votes
2 answers
2k views

Continuous maps which send intervals of $\mathbb{R}$ to convex subsets of $\mathbb{R}^2$

Let $f : \mathbb{R} \longrightarrow \mathbb{R}^2$ be a continuous map which sends any interval $I \subseteq \mathbb{R}$ to a convex subset $f(I)$ of $\mathbb{R}^2$. Is it true that there must be a ...
Abcd's user avatar
  • 629
63 votes
6 answers
4k views

Shortest closed curve to inspect a sphere

Let $S$ be a sphere in $\mathbb{R}^3$. Let $C$ be a closed curve in $\mathbb{R}^3$ disjoint from and exterior to $S$ which has the property that every point $x$ on $S$ is visible to some point $y$ of $...
Joseph O'Rourke's user avatar
45 votes
4 answers
5k views

Polynomial roots and convexity

A couple of years ago, I came up with the following question, to which I have no answer to this day. I have asked a few people about this, most of my teachers and some friends, but no one had ever ...
44 votes
11 answers
25k views

Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
Xerxes's user avatar
  • 441
41 votes
6 answers
2k views

Approximating a convex disk by an ellipse

For every convex compact set $K$ of area $1$ in $\mathbb{R}^2$, among all ellipses of area $1$ there exists an ellipse $E$ such that the area of the symmetric difference between $K$ and $E$ is ...
Wlodek Kuperberg's user avatar
39 votes
2 answers
1k views

Abstract definition of convex set

I'd like to formulate an abstract definition of convex sets: a set $K$ is convex if it is endowed with a ternary operation $K\times[0,1]\times K\to K$, written $(x:t:y)$, satisfying axioms $(x:0:y)=(...
grok's user avatar
  • 2,489
38 votes
7 answers
5k views

Shortest path connecting two opposite points on a cube

Is it true, that a path connecting two opposite points (i.e. such that the segment joining them passes through the centre of mass of the cube) on the surface of the $d$-dimensional unit cube (with $d&...
Arseniy Akopyan's user avatar
38 votes
2 answers
2k views

How to make a sandwich from just one piece of bread?

I don't know how to go about such questions. It's not exactly my area, so maybe it is stupid, but curiosity is winning. So I have a piece of bread $P$ of a really non-regular shape (let's make it ...
erz's user avatar
  • 5,385
37 votes
0 answers
1k views

Converse of the Archimedean property of the sphere

In his remarkable book On the Sphere and Cylinder, where he came tantalizingly close to discovering calculus, Archimedes showed that the area of the portion of the sphere contained between a pair of ...
Mohammad Ghomi's user avatar
36 votes
0 answers
1k views

Two-convexity ⇒ Lefschetz?

Assume that $\Omega$ is an open simply connected set in $\mathbb R^n$ (two-convexity) if 3 faces of a 3-simplex belong to $\Omega$ then whole simplex in $\Omega$. Is it true that any component of ...
Anton Petrunin's user avatar
35 votes
1 answer
2k views

Which polygons can be turned inside out by a smooth deformation?

Take a non-degenerate polygon with side lengths $\{a_1,\dots,a_n\}$ in a convex configuration. What is the condition on the $a_i$'s so that the polygon can be turned inside out by a continuous motion ...
Ivan Meir's user avatar
  • 4,782
34 votes
6 answers
6k views

How to explain the concentration-of-measure phenomenon intuitively?

One way to phrase the "concentration-of-measure" phenomenon is that, for a Euclidean sphere $S^d$ in $d$ dimensions, for large $d$, "most of the mass is close to the equator, for any equator."1 Q. ...
Joseph O'Rourke's user avatar
33 votes
3 answers
2k views

Polar body of a convex body that avoids a lattice

Let $K \subset {\bf R}^d$ be a symmetric convex body (an open bounded convex neighbourhood of the origin with $K = -K$) with the property that $K + {\bf Z}^d \neq {\bf R}^d$, i.e. the projection of $K$...
Terry Tao's user avatar
  • 108k
31 votes
2 answers
2k views

The logic of convex sets

Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
darij grinberg's user avatar
28 votes
2 answers
964 views

Can we always shift two disjoint convex bodies a little bit to decrease the volume of their convex hull?

Let $K,L\subset\mathbb R^d$ be two disjoint compact convex sets with non-empty interiors. Can $x=0$ be a point of local minimum for the function $F(x)=\text{vol}_d(\text{conv(K,L+x))}$? I was asked ...
fedja's user avatar
  • 59.5k
28 votes
1 answer
1k views

Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)

This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
Harry Altman's user avatar
  • 2,535
28 votes
0 answers
537 views

Can every 3-dimensional convex body be trapped in a tetrahedral cage?

Can every 3-dimensional convex body be trapped in a tetrahedral cage? Although the question is fairly unambiguous, I give all relevant definitions: $\bullet$ A subset $C$ of $\mathbb{R}^n$ is an $n$-...
Wlodek Kuperberg's user avatar
26 votes
3 answers
1k views

Largest possible volume of the convex hull of a curve of unit length

What is the largest possible volume of the convex hull of an open/closed curve of unit length in $\mathbb{R}^3$?
Vladimir Reshetnikov's user avatar
25 votes
4 answers
3k views

Analogy of Parseval identity for Legendre Transform ?

Parseval's identity states that the sum of squares of coefficients of the Fourier transform of a function equals the integral of the square of the function, or $$ \sum_{-\infty}^{\infty} |c_n|^2 = (1/...
Suresh Venkat's user avatar
25 votes
4 answers
1k 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 ...
Cecil B's user avatar
  • 253
25 votes
3 answers
3k 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 ...
Gregor Samsa's user avatar
25 votes
4 answers
3k views

Ellipse naturally associated with a polygon

My colleagues and I have stumbled onto a way to associate an ellipse, or equivalently a positive definite symmetric matrix, to a polygon that is different from other better known ways. We want to know ...
Deane Yang's user avatar
  • 26.9k
24 votes
3 answers
1k views

Average measure of intersection of a convex region with its translate

Let $\lambda$ denote the Lebesgue-measure on $\mathbb{R}^n$, and let $C\subset\mathbb{R}^n$ be a convex region. My question is about $$f(C):=\int_{C} \lambda(C \cap (x + C) ) \mathrm{d} x.$$ How ...
zref's user avatar
  • 343
24 votes
1 answer
1k views

Which natural numbers are a square minus a sum of two squares?

Question: Which natural numbers are of the form $a^2 - b^2 - c^2$ with $a>b+c$? This question came up in (Eike Hertel, Christian Richter, Tiling Convex Polygons with Congruent Equilateral ...
Andreas Thom's user avatar
  • 25.3k
24 votes
1 answer
521 views

What is the minimal volume of the intersection of a self-dual cone and the unit ball?

When thinking of some other problem, I stumbled upon the following innocently looking question that is natural enough to have been considered (and, possibly, solved) many years ago. However my ...
fedja's user avatar
  • 59.5k
23 votes
1 answer
647 views

Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks

Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...
Mohammad Ghomi's user avatar
22 votes
5 answers
1k views

Is the diameter of a centrally symmetric convex body realized by a pair of antipodal points?

Let $S \subset \mathbb{R}^n$ be the boundary of a centrally symmetric convex body and provide $S$ with the geodesic metric given by its embedding in Euclidean space (i.e., the distance between two ...
Alfredo Hubard's user avatar
22 votes
2 answers
1k views

Do the elementary properties of mixed volume characterize it uniquely?

Background Take 2 convex sets in $\mathbb{R}^2$, or 3 convex sets in $\mathbb{R}^3$, or generally, $n$ convex sets in $\mathbb{R}^n$. "Mixed volume" assigns to such a family $A_1, \ldots, A_n$ a ...
Tom Leinster's user avatar
  • 27.2k
21 votes
5 answers
1k views

Is there a midsphere theorem for 4-polytopes?

The (remarkable) midsphere theorem says that each combinatorial type of convex polyhedron may be realized by one all of whose edges are tangent to a sphere (and the realization is unique if the center ...
Joseph O'Rourke's user avatar
21 votes
2 answers
1k views

Structures of the space of neural networks

A neural network can be considered as a function $$\mathbf{R}^m\to\mathbf{R}^n\quad \text{by}\quad x\mapsto w_N\sigma(h_{N-1}+w_{N-1}\sigma(\dotso h_2+w_2\sigma(h_1+w_1 x)\dotso)),$$ where the $w_i$ ...
pglpm's user avatar
  • 313
21 votes
2 answers
1k views

On convergence of convex bodies

Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$. Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any $0<\...
asv's user avatar
  • 21.1k
20 votes
4 answers
906 views

The limit of edge-midpoint convex polyhedra

    Starting with a convex polyhedron $P_1 \subset \mathbb{R}^3$, replace that with $P_2$, the convex hull of the midpoints of the edges of $P_1$. Continuing this process, we obtain a ...
Joseph O'Rourke's user avatar
20 votes
2 answers
871 views

A functional inequality about log-concave functions

Let $f,g$ be smooth even log-concave functions on $\mathbb{R}^{n}$, i.e.,$f=e^{-F(x)}, g=e^{-G(x)}$ for some even convex functions $F(x),G(x)$. Is it true that: $$ \int_{\mathbb{R}^{n}} \langle \...
Paata Ivanishvili's user avatar
19 votes
3 answers
2k views

Cutting convex sets

Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference. Can one cut every bounded convex set of the Euclidean plane into an arbitrary number $...
Roland Bacher's user avatar
19 votes
1 answer
931 views

Where to find some subset of Khovanskii's 15 proofs of the BKK theorem?

(I asked this question on MSE, but someone suggested it would be better asked here.) I'm a fan of the Bernstein-Khovanskii-Kushnirenko theorem (that the number of solutions in $(\mathbb{C}^*)^n$ to a ...
Will Dana's user avatar
  • 453
19 votes
0 answers
621 views

Is there a simpler proof of the key lemma in the paper by Hiroshi Iriyeh and Masataka Shibata on the 3D Mahler conjecture?

In this remarkable paper 30 pages are occupied by the proof of the following innocently looking lemma: Let $K$ be an origin-symmetric convex body in $\mathbb R^3$. There exist three planes through ...
fedja's user avatar
  • 59.5k
18 votes
2 answers
825 views

Reference to a conjecture on unit vectors in Euclidean space

I have heard that there exists the following conjecture (if I am not mistaken). Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists another unit vector ...
asv's user avatar
  • 21.1k
18 votes
3 answers
3k views

Deciding membership in a convex hull

Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$. This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
Mitch's user avatar
  • 657
18 votes
3 answers
918 views

Convex functions in convex sets

Suppose $\Omega \subset \mathbb{R}^n$ is some bounded, convex set. For which domains $\Omega$ is it true that for every convex function $f:\Omega \rightarrow \mathbb{R}$ the average of the function in ...
Stefan Steinerberger's user avatar
18 votes
3 answers
2k views

Are the Platonic solids shadows of 4-polytopes?

Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection). I am wondering if each of the five ...
Joseph O'Rourke's user avatar
18 votes
1 answer
902 views

Is the ball reducible in some high dimension?

Let $K$ be a bounded symmetric ($-K=K$) open convex body in $\mathbb R^n$. The critical determinant $d(K)$ of $K$ is the least possible volume $|\operatorname{det}(a_1\dots a_n)|$ of the fundamental ...
fedja's user avatar
  • 59.5k
17 votes
3 answers
6k views

The cone of positive semidefinite matrices is self-dual? (reference needed)

I'm seeking a reference for the following fact. The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar). This result is relatively easy to prove, has been known for a long time,...
Louis Deaett's user avatar
  • 1,513
17 votes
1 answer
519 views

Does the boundary of a convex body contain a regular planar pentagon?

How to prove or disprove that the boundary of any convex body in $\mathbb{R}^3$ includes 5 points which form a regular planar pentagon? The following consideration suggests the answer "yes": if we ...
user64494's user avatar
  • 3,309
17 votes
2 answers
978 views

Placing points on a sphere so that no 3 lie close to the same plane

Motivation I am working with arbitrary parallelopiped tilings given by projection from a higher dimensional space. The collection of tiles, and some properties of the higher dimensional space are ...
Edmund Harriss's user avatar
17 votes
0 answers
369 views

Talagrand's "Creating convexity" conjecture

We say a subset $A$ of $\mathbb{R}^N$ is balanced if \begin{equation} x \in A, \lambda \in [-1,1] \implies \lambda x \in A. \end{equation} Given a subset $A$ of $\mathbb{R}^N$, we write \begin{...
Samuel Johnston's user avatar
17 votes
0 answers
361 views

Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?

Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation it stays a convex polytope, it stays a combinatorial dodecahedron (i.e. its ...
M. Winter's user avatar
  • 12.5k
16 votes
5 answers
1k views

A characterization of convexity

While doing some research on polytopes I came to the following question. Maybe it's already somewhere but anyway I'll post it here. Let $X\subset \mathbb{R}^3$ be such that, for every plane $P$, $P\...
Cristos A. Ruiz's user avatar
16 votes
3 answers
902 views

What is known about sufficient conditions for the rigidity of a convex surface?

A convex surface is a connected open subset of the boundary of a convex body in $\mathbb{R}^3$. An "infinitesimal bending" of a convex surface $S$ is a deformation of $S$ given by a velocity field $v:...
Eben Kadile's user avatar
16 votes
1 answer
1k views

Optimal 8-vertex isoperimetric polyhedron?

I know from Marcel Berger's Geometry Revealed: A Jacob's Ladder to Modern Higher Geometry (p.531) that it is not yet established which polyhedron in $\mathbb{R}^3$ on 8 vertices achieves the optimal ...
Joseph O'Rourke's user avatar

1
2 3 4 5
21