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 ...
2
votes
2answers
99 views

Worst-case nearest-neighbor distances between regions

Suppose that $S_1,\dots,S_n$ is a collection of disjoint shapes in the plane, and let $\mathcal{X}$ denote the set of all $n$-tuples of points $\lbrace x_1,\dots,x_n\rbrace$ such that $x_i\in S_i$ for ...
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 ...
1
vote
0answers
160 views

Finding a curve of some approximate arc length (with uniform or zero curvature) with a specified distance to a set of points in 3-space

Imagine I define a set of $N$ points in 3-space, $P$, and I would like to define a straight-line or curve, $C$, with uniform or zero curvature, that has some desired distance, $M$, to each of these ...
4
votes
0answers
87 views

Applications of k-medians with moment constraints

Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the Euclidean $k$-medians (or $k$-means) problems, our objective is to distribute a set of $k$ points $x_1,\dots,x_k$ in the ...
6
votes
1answer
269 views

Constructing a hypersurface with given outer normals

Pick a point on each of the positive half-axes in $\mathbb{R}^n$. Put a (unit-norm?) vector at each of the n points. (a) Is there a hypersurface in the orthant $\mathbb{R}^n_+$ going through these n ...
2
votes
1answer
333 views

Feasible space of SDP

Typically the non-empty feasible space of a SDP has some curved boundary which is why the feasible space has infinitely many extreme points. Is it ever possible to have a SDP whose non-empty feasible ...
20
votes
2answers
1k views

Functions whose gradient-descent paths are geodesics

Let $f(x,y)$ define a surface $S$ in $\mathbb{R}^3$ with a unique local minimum at $b \in S$. Suppose gradient descent from any start point $a \in S$ follows a geodesic on $S$ from $a$ to $b$. (Q1.) ...
1
vote
2answers
217 views

how to estimate a polyhedron(convex hull) classifier from data sample

Given a set of points $X\in\Re^D$, they have labels $Y\in${$-1,+1$}. I would like to separate the data labeled +1 and the data labeled -1 by a polyhedron. $min_w \sum_i \xi_i + \frac{1}{2}\|w\|_2^2$ ...