The tag has no wiki summary.

learn more… | top users | synonyms

36
votes
4answers
2k 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 noone had ever ...
8
votes
3answers
1k views

Listing lattice points in a simplex

Let $n \in \mathbf{Z}_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v_0,\dots,v_n \in \mathbf{Z}^n$, computes the set $\Delta ...
9
votes
0answers
325 views

How aspherical can a Gömböc be?

A Gömböc is a homogeneous massive convex solid that can rest on a horizontal plane in just two positions of equilibrium under gravity: one stable and the other unstable. How small a proportion of the ...
30
votes
0answers
913 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 ...
3
votes
2answers
376 views

Submanifolds lying on the boundary of a convex domain

Let $M$ be a submanifold of $\mathbb R^n$. Call $M$ locally convex if locally $M$ is contained in the boundary of a convex domain of $\mathbb R^n$. Is there any known condition that is equivalent to ...
17
votes
4answers
1k 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 = ...
12
votes
2answers
605 views

Point on a line nearest a point in Banach space

I have a Banach space geometry question (a curiosity-driven spin-off from a research topic). Given a point $x$ on the unit sphere of a Banach space and a vector $y\ne 0$, there is a multiple $t_0y$ of ...
7
votes
3answers
507 views

sharper minkowski bound

If we want to bound the norm of the smallest ideal which generates a nontrivial ideal class, is there a better bound than Minkowski's bound? (Note that Minkowski's bound is to guarantee something ...
8
votes
2answers
484 views

Do elongated convex objects all have long simple geodesics?

Let $S$ be a closed convex surface, the boundary of a compact convex body in $\mathbb{R}^3$. I am interested in whether there are conditions on its shape that ensure that it supports a long, simple ...
2
votes
2answers
973 views

Finding points inside innermost convex hull [closed]

Given a set of points $S$ on the Euclidean plane, Onion Peeling determines the nested set $H$ of convex hulls on $S$. Define an analytical formula on $S$ which produces a point, not necessarily in ...
1
vote
1answer
295 views

How do maximum norms relatively change in Euclidean translations

Let $Q$ be the cube $[-1,1]^{3}$ and $\pi$ be a plane in $\mathbb{R}^{3}$ that contains the origin but doesn't contain any vertex of $Q$. Suppose that $A$ is an invertible linear transformation from ...
1
vote
1answer
190 views

crookedness of convex curves (milnor)

hello, I'm currently reading On the Total Curvature of Knots and am trying to understand one of the lemmas in it (3.3) A closed polygon $P$ in $H^2$ is convex if and only if for every $b$ either ...
1
vote
1answer
262 views

The number of hyperplanes determining the integer points of a polyhedron

This question is inspired by this one. Let $P \subset \mathbb R_{+}^n$ be a convex polyhedron whose complement in $\mathbb R_{+}^n$ has finite volume. Let $Int(P) = P \cap \mathbb N^n$. (For ...
21
votes
4answers
1k 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 ...
1
vote
2answers
599 views

Is there always a parallelogram cross-section of parallelepiped contained in the smallest box

Let $M$ be a centered parallelepiped, the intersection of $M$ and any plane $P$ that passes through the origin is a parallelogram or hexagon. Each parallelogram or hexagon has a cubic box that is the ...
1
vote
0answers
386 views

Does the dual Banach space $B(\ell^\infty)$ have weak* normal structure?

Let $K$ be a bounded closed convex subset of a Banach space $E$. A point $x$ in $K$ is called a diametral point if $$ \sup_{y\in K} \|x-y\|={\rm diam}(K). $$ where ${\rm diam}(K)$ denotes the ...
21
votes
2answers
1k 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 ...
3
votes
1answer
352 views

A conjecture of parallelogram inside convex and central symmetric curve

Assume Q is a convex central symmetric curve, whose area is $\displaystyle S$. The area of the maximum parallelogram inside Q is $\displaystyle S'$. How to prove the conjecture that $\displaystyle ...
8
votes
1answer
192 views

Finding a point that lies in a majority of polytopes

Suppose I have $k$ $n$-dimensional polytopes $P_1,\ldots,P_k$, each explicitly specified as the intersection of a collection of hyperplanes. If there was a point $p \in \mathbb{R}^n$ that lay in the ...
2
votes
0answers
116 views

Quantifying that near a point on a smooth hypersurface, it looks like a tangent hyperplane

Suppose $C$ is a smoothly bounded convex body (*) in $\mathbb{R}^d$, and $p$ is a point on the boundary of $C$. Let $r>0$ and let $B(r)$ denote the ball of radius $r$ centered at $p$. Is it ...
0
votes
3answers
525 views

a different algebra/representation for convex sets

Hi, I was dealing with finding a feasible region for a set of norm inequalities and the feasible region is convex. The question is not about how to find the feasible region but how to represent the ...
5
votes
2answers
356 views

Isodiametric hull

Let A be a convex compact set in the plane (with a piecewise smooth boundary, say). We want to `inflate' it in such a way that the diameter does not increase. More accurately, we are looking for ...
3
votes
0answers
125 views

Dimension of convex arrangements for hypergraphs

Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A. Has ...
26
votes
3answers
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 ...
3
votes
3answers
993 views

Estimate probability( 0 is in the convex hull of N random points ) ?

Can anyone estimate N such that Prob( 0 is in the convex hull of $N$ points ) >= .95 for points uniformly scatterered in $[-1,1]^d$, $d = 2, 3, 4, 10$ ? The application is nearest-neghbour ...
2
votes
1answer
630 views

Condition number for Ellipsoid method matrix

Hello, When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$. ...
11
votes
5answers
738 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$, ...
7
votes
1answer
433 views

A variation of Minkowski sum

I have to work with the following variation of Minkowski sum: Let $\mathbb E$ be a Euclidean space and $K$ be a convex set in $\mathbb E\times \mathbb E$. Set $$K^+=\{\\,x+y\in\mathbb ...
11
votes
1answer
387 views

Pushing convex bodies together

Given two convex bodies $A$ and $B$, in $\mathbb R^3$ let's say. We define $A(t)$ and $B(t)$ as $A+xt$ and $B+yt$ where $x,y$ are two arbitrary points. (That is the Minkowski sum, so the two bodies ...
11
votes
0answers
666 views

Constructive aspects of Caratheodory's theorem in convex analysis

Let me paraphrase Caratheodory's theorem in a probabilistic setup: Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
16
votes
3answers
1k 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 ...
0
votes
1answer
1k views

Minimum enclosing rectangle of a convex polygon proof

Hi, I've been reading about the rotating calipers algorithm for solving the minimum-area enclosing rectangle problem. It relies on a theorem: The rectangle of minimum area enclosing a convex polygon ...
4
votes
1answer
193 views

Diameter of a metric on orbits under affine bijections of $n-$dimensional convex compact sets

Given two $n-$dimensional convex compact sets $A,B$, we define $d(A,B)$ as $\log({\mathrm{Vol}}(\alpha_2(A)))-\log(\mathrm{Vol}(\alpha_1(A)))$ where $\alpha_1,\alpha_2$ are two affine bijections such ...
5
votes
2answers
454 views

Applications of Cauchy's Arm Lemma

Cauchy's Arm Lemma is used in the proof of Cauchy's Rigidity Theorem for convex polyhedra. The Lemma states that in the plane or on the sphere that if all but one of the side lengths of two convex ...
1
vote
1answer
774 views

Geometric interpretation of singular values

The singular values of a matrix A can be viewed as describing the geometry of AB, where AB is the image of the euclidean ball under the linear transformation A. In particular, AB is an elipsoid, and ...
3
votes
1answer
151 views

Edge-maximizing projective transformation on polytopes

Let P and Q be simple polytopes such that P = Q ∩ H and let H be a halfspace with normal vector n. Let projn(e) denote the length of the projection of edge e onto vector n. Consider the set E of ...
5
votes
2answers
335 views

Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
11
votes
3answers
625 views

Continuous automorphism groups of normed vector spaces?

Consider the metric space on, say, ℝ2 induced by the various $L^p$ norms, and the group of isometries from that space into itself that preserve the origin. When $p=2$ I get the continuous group ...
5
votes
2answers
700 views

Maximal Ellipsoid

John's Theorem can be stated as "To every compact, convex body, there is a unique inscribed ellipsoid, whose volume is maximal among all inscribed ellipsoids." It goes on to classify this maximal ...
10
votes
3answers
617 views

Deciding membership in a convex hull

Problem: 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 ...
1
vote
1answer
377 views

Is the direction of the longest line of a polytope unique?

The question pertains to a polytope that is generated by the intersection of an affine subspace with a hypercube in $p$ dimensions. The affine subspace is given by: $X \mbox{ u} = y$ where $u$ ...
5
votes
0answers
409 views

Generalizations of generators / hyperplanes descriptions for cones to partially-ordered fields?

Background: given a finite-dimensional real vector space V of dimension d, I can define a pointed cone in two ways: either as a set of the form $\{r_1v_1 + \cdots + r_nv_n \mid r_1, \dots, r_n \in ...
1
vote
2answers
1k views

Break Polyhedron into Tetrahedron

Given a polyhedron consists of a list of vertices (v), a list of edges (e), and a list of surfaces connecting those edges (...
15
votes
9answers
7k 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 ...