3
votes
0answers
58 views

Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...
7
votes
3answers
312 views

The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small? More ...
14
votes
3answers
643 views

“Entropy” proof of Brunn-Minkowski Inequality?

I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality. The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then $$ ...
2
votes
1answer
159 views

Upper bounds on the worst-case traveling salesman tours in the unit square

The paper [1] proves that, if we place $N$ points in the unit square, then the length $\ell$ of the euclidean TSP tour of those points must satisfy $$\ell \leq \sqrt{2N} + 7/4~~.$$ I'm wondering, can ...
6
votes
1answer
239 views

Generalization of the equilateral triangle?

I consider points in the two-dimensional plane. An equilateral triangle is a set of three points in the plane which are equidistant. Suppose now I have $n$ points $x_1,...,x_n$. What is the ...
3
votes
1answer
192 views

Riemannian metric on a space of “not-quite-smooth” (hyper)surfaces?

Apologies if the title's a bit vague; I'll try to explain everything below, and please let me know if I should clarify anything. I've been looking for a while at variational problems on polytopes. ...
2
votes
0answers
144 views

Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram

Suppose I'd like to distribute a set of points $P=\lbrace p_1 ,\dots, p_n \rbrace$ in the unit square $S=[0,1]\times[0,1]$ to minimize a weighted sum of two things: 1) The average distance between a ...
4
votes
0answers
124 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 ...
5
votes
1answer
263 views

Geometric applications of Ekeland's variational principle

I'm looking for geometric applications of Ekeland's variational principle in order to see it at work in a context I'm familiar with. Let me recall the principle itself: Definition. Let $(X,d)$ be a ...
11
votes
3answers
475 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} ...
7
votes
2answers
347 views

More general form of inequality?

I have proved a simple Lemma that I need for a larger result, and I was wondering whether it is actually another more famous result in disguise. The lemma says that for any set of vectors in ...
8
votes
2answers
338 views

An extension of Gaussian Isoperimetry

The Gaussian isoperimetric inequality (Tsirelson,Sudakov, Borell) states that among all sets of given Gaussian measure in the n-dimensional Euclidean space, half-spaces have the minimal Gaussian ...
2
votes
1answer
216 views

Maximum distance of points in intersection of balls

Dear all, let $B_\delta(p):=\{x\in\mathbb{R}^d:||x-p||_2\leq \delta\}$ be a $d$-dimensional closed ball. Now I do not have one ball, but four: $B_{r_1}(p)$, $B_{r_2}(p)$, $B_{s_1}(q)$ and ...
3
votes
3answers
786 views

Minimum norm of convex hull

Dear all, I am currently stuck at a problem which seems too easy to be stuck at to me... Summary Let $H$ be the convex hull of the points $d_1,\ldots, d_n\in \mathbb{R}^d$. How can one compute ...
13
votes
1answer
2k views

A circle packing conjecture

Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and ...
6
votes
3answers
407 views

Sequences of evenly-distributed points in a product of intervals

Let φ be the golden ratio, (1+√5)/2. Taking the fractional parts of its integer multiples, we obtain a sequence of values in (0,1) which are in some sense "evenly distributed" in a way which ...
5
votes
1answer
596 views

Minimizing variance of distances between points when mean distance is fixed

In Rd, I have n > d+1 points. The mean distance between pairs of points is 1. How can I minimize the variance of the distances (equivalently, the mean squared distance)? I'm mainly interested in d ...
4
votes
0answers
283 views

The Gömböc and monostatic objects

This made the popular news a few years ago. Summary: it's the first homogeneous, convex solid to be found with only one stable and one unstable mechanical equilibrium when resting on a flat surface. I ...
3
votes
2answers
280 views

Optimizing the layout of Infinite Suburbia

Infinite Suburbia is a Euclidean plane, P. All residents live in open unit disks which, like caravans, can travel around but are stationary most of the time. When stationary, these disks lie in a ...
9
votes
2answers
2k views

An optimization problem for points on the sphere (master's dissertation)

First, by means of a disclaimer, some background. I am entering the fourth and final year of an undergraduate master's degree in maths, and a quarter of the maximum credit for this year will be for a ...
22
votes
2answers
1k views

What is the best way to peel fruit?

A mango made me wonder about this. (See also this question, which is in a similar spirit.) Fix $L >0$ and a smooth body (possibly nonconvex—pears or bananas are fair game!) $B \subset ...
2
votes
1answer
96 views

Optimizing finite-length approximations to space-filling loops

Take a loop in the unit disk D^2, with length l where length is defined as the supremum of the lengths of piecewise linear approximations. What is the smallest r such that every radius-r subdisk of ...
2
votes
2answers
539 views

Are Bregman divergences quasi-convex?

Given a convex set S ⊂ ℝd and an appropriately differentiable convex function f: S → ℝ, a Bregman divergence Bf(x, y) = f (x) - f (y) -⟨x- y , ∇f (y)⟩ for x, y ...
3
votes
2answers
582 views

Problem equivalent to “largest square in a cube”

The "largest square in a cube" problem, which asks for the largest square inside a cube, has a solution as can be seen on this page, which also says that the general problem in higher dimensions is ...
3
votes
1answer
1k views

Maximizing Sparsity in l1 Minimization?

Consider the optimization problem $$\min_x ||Ax||_1 + \lambda||x-b||^2,$$ where $A \in \mathbb{R}^{n \times n}$, $x,b \in \mathbb{R}^n$ and $\lambda$ is strictly greater than 0. (This problem is ...
5
votes
3answers
607 views

How can I embed an N-points metric space to a hypercube with low distortion?

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of ...
0
votes
2answers
2k views

If a quadratic form is positive definite on a convex set, is it convex on that set?

Consider a real symmetric matrix $A\in\mathbb{R}^{n \times n}$. The associated quadratic form $x^T A x$ is a convex function on all of $\mathbb{R}^n$ iff $A$ is positive semidefinite, i.e., if $x^T A ...
2
votes
2answers
304 views

High dimensional Steiner tree

Given n affinely independent points in n-1 dimensional Euclidean space, how is the minimum Steiner tree constructed? Or assuming that the topology of the Steiner tree is given, is there an easy way ...