5 votes

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 ...
user avatar
  • 143k
5 votes
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 ...
user avatar
  • 143k
5 votes
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 ...
user avatar
  • 5,722
4 votes
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 ...
user avatar
4 votes

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 ...
user avatar
3 votes
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 ...
user avatar
3 votes
Accepted

How to detect intersecting segments based on length of the segments

First assume that you know where $A,B,C,D$ are. In this case, you can write $D$ uniquely in the form $\alpha_A A + \alpha_B B + \alpha_C C$, with $\alpha_A + \alpha_B + \alpha_C = 1$. The tuple $(\...
user avatar
  • 2,886
3 votes
Accepted

Why is it hard to show that the euclidean Steiner tree problem is in NP?

I'm guessing the difficulty lies in the fact that euclidean distance is involved, and we don't know if comparing sums of integrer square roots is in NP. The problem is the following: for integers $a_1,...
user avatar
  • 2,209
3 votes
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 ...
user avatar
  • 554
3 votes

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 ...
user avatar
  • 10.8k
3 votes
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 ...
user avatar
  • 4,440
2 votes

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 ...
user avatar
  • 25.4k
2 votes
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 ...
user avatar
  • 143k
2 votes
Accepted

Splitting a set of points in the plane evenly and sorting it

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 ...
user avatar
2 votes
Accepted

Counting arrays with Euclidean distance at most 2 from a given binary array

Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units. Since your arrays are binary, $$(A_i-B_i)^2 = \begin{...
user avatar
2 votes
Accepted

How to embed Pearson distance into Euclidean space

Yes. Normalize the vectors, then use the Euclidean ($L_2$) distance. In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector $$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$ where $\mu=(v_1+...
user avatar
  • 143k
2 votes

Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern ...
user avatar
  • 689
2 votes
Accepted

Find the placement of gates on 2D points that minimizes the total distance of all paths to be made

Based on the reformulation of your problem from Bernardo Subercaseaux, your problem is NP-hard (as John L explains), so you should not expect an algorithm that will be efficient in the worst case. ...
user avatar
  • 143k
1 vote
Accepted

Efficient intersection detection between disks with identical radius

Use any standard data structure / algorithm for nearest neighbor search. In particular, you are interested in the fixed-radius nearest neighbor problem, for which there are many algorithms.
user avatar
  • 143k
1 vote

A heuristic for finding the vector that is maximally distant from a set of vectors

Just to answer with some ideas. If you have too many dimensions, you can use the Johnson–Lindenstrauss lemma to reduce the dimensions while keeping distances approximately the same (some $\epsilon$ ...
user avatar
  • 13.3k
1 vote
Accepted

Computing the minimum distance between each pain of points

Suppose the points are $[4,1,10,11]$. The distance from the starting point (whether you interpret that as $4$ or $1$) to each other point does not give you the nearest pair of points. In this ...
user avatar
  • 143k
1 vote

Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

The best I can come up with is to compute the centroid of each object and store the centroids in a nearest-neighbor data structure; to find the matches for a test object $T$, look up its centroid in ...
user avatar
  • 143k
1 vote

Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

Suppose $G$ is a weighted graph, and $T_{OPT}$ is the optimal route you seek. For clarity: $T_{OPT}$ is a path that connects all vertices, such that for any other path $P$ that connects all vertices,...
user avatar
  • 1,635
1 vote
Accepted

Closest k points - performance on large lists

I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points. ...
user avatar
  • 689
1 vote
Accepted

expected pairwise square euclidean distance between points

Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $[0,1]^d$. That is, $x_1,\ldots,x_d,y_1,\ldots,y_d$ are all uniform random samples of the uniform ...
user avatar
1 vote
Accepted

In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific ...
user avatar
1 vote
Accepted

Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid

It is nice that you try to draw a comparison between two similar situations. However, it looks like you are driving too fast to stay on the right road. Henceforth I will be moving somewhat slowly so ...
user avatar
  • 34.7k
1 vote

Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation

The asymptotic complexity for the worst case is the same. Actually, the constant factors will be quite close together on a typical modern processor - if you don't calculate the execution time ...
user avatar
  • 25.4k
1 vote

Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation

The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption). The practical running time may be ...
user avatar
  • 143k
1 vote

Algorithm to mimimally pair up points in 3D space

As an approximate solution in $O(n^2)$ you can construct the cost matrix $M$ and then solve the stable marriage problem.
user avatar
  • 12.4k

Only top scored, non community-wiki answers of a minimum length are eligible