Tagged Questions

614 views

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 $$... 1answer 156 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 ... 1answer 237 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 ... 1answer 191 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. ... 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 ... 0answers 123 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 ... 1answer 262 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 ... 3answers 473 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} ... 2answers 346 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 ... 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 ... 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 ... 3answers 783 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 ... 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 ... 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 ... 1answer 595 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ...
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 ...