# Tag Info

### Recovering a point embedding from a graph with edges weighted by point distance

One algorithmic approach to solving this problem: treat this as a set of nodes, connected by springs, then let them settle/relax into shape. Each edge $(v,w)$ corresponds to a spring; if the distance ...
Accepted

### Can the Euclidean distance function be computed using only XOR's

No. It's not possible. Any function that can be computed using just XOR's is affine over $GF(2)$. However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it ...
Accepted

### Recovering a point embedding from a graph with edges weighted by point distance

The problem is NP-Complete. The positions of the points is a good certificate, so it's in NP, and you can encode circuits into the "is there a satisfying set of points?" problem. Reduction from ...
Accepted

### Should planar Euclidean graphs be planar straight-line graphs?

Fáry's theorem states that every planar graph can be drawn in such a way that its edges are (non-crossing) straight lines. Hence every planar graph is a planar straight-line graph. However, this ...

### Recovering a point embedding from a graph with edges weighted by point distance

Partial answer on uniqueness: 3-connectedness is not sufficient. Minimal counter example: cube graph ($Q_3$ of the Hypercube Graph family) To see how fixing the length of all edges in $Q_3$ does not ...
Accepted

### Embedding from $L^\infty$ space to $L^2$ space

The answer is unfortunately negative in general, by combining the following two well-known facts: Every metric space on $n$ points embeds isometrically into $(n-1)$-dimensional $L^\infty$. Embedding ...
Accepted

Accepted

### Finding Euclidean Minimum Spanning Tree

If you're asking this question because you want something easier to implement than a Delaunay triangulation algorithm you're most likely out of luck. You should also specify in what space you're ...

### Recovering a point embedding from a graph with edges weighted by point distance

this is known as the following problem and occurs eg with reconstructing coordinates from sensor networks that can measure distance to nearby nodes, & this paper can serve as a mini-survey along ...
Accepted

### Finding smallest triangle to fit all points

If the triangle is centered at the origin, in general only one point touches it. You find this point as the one furthest in the three directions normal to the triangle sides (by taking the dot product ...

### How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance

That is a long solved problem. First, if you are using double precision floating point numbers in IEEE754 format (which is most common), that's what extended precision was invented for. Even in the ...
Accepted

### Efficient algorithm to fulfil a set of coordinate constraints

The simplest approach (in terms of programming effort) might be to try using an existing graph layout tool. Those solve a related problem: given a graph with distances on the edges, try to find the ...
This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points ...