Questions tagged [euclidean-distance]
The euclidean-distance tag has no usage guidance.
30
questions
2
votes
1answer
33 views
Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights
I'm looking for an algorithm that gives a smallest value of 'travel cost' within the following constraints:
a complete, connected, weighted graph,
vertices are defined in 3d euclidean space,
...
1
vote
1answer
27 views
Closest k points - performance on large lists
Very similar to this
Problem formulation: Given a list $L$
of n points with GPS coordinates and a second list $Q$ of $m$ points, find the $k$ (let's say 3) closest points on $L$ for each element on $...
2
votes
0answers
63 views
Stable and fast computation of the squared euclidean distance matrix
Let's say I want to compute the matrix $M$ of the squared euclidean distances between each pair of vectors $(x, y)$ belonging to two sets $X$ and $Y$ respectively. The sets of vectors $X$ and $Y$ have ...
2
votes
0answers
103 views
Sub-optimal and fast solutions to assignment problem
I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem.
Are ...
0
votes
0answers
17 views
Johnson-Lindenstrauss and k-means
I have a question about Johnson-Lindenstrauss and k-means.
I m study a resource that explain a link between Johnson-Lindenstrauss and k-means.
From what I understand, Johnson-Lindenstrauss helps us ...
3
votes
1answer
180 views
expected pairwise square euclidean distance between points
How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$?
Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-...
1
vote
1answer
142 views
In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?
In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for ...
0
votes
1answer
46 views
Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid
There are two questions that I am trying to draw a comparison between:
...
0
votes
1answer
163 views
Finding Euclidean Minimum Spanning Tree
Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization.
We can solve this problem with Prim's algorithm in $O(n^2)...
1
vote
0answers
20 views
In multiobjective optimization, how to calculate the distance to reference point?
In multiobjective optimization, what does the distance exactly means, is it:
1) The distance from reference point (V) to an individual (Xi) (candidate solution) in the population (decision space).
<...
0
votes
0answers
60 views
Clustering non-overlapping time series
I have thousands of times series of different length and different time. I want to group them together so that I know the optimal ones to pick as input for a ML algorithm and to document how they are ...
2
votes
0answers
21 views
Partial TSP in Euclidian plane
I'm interested in the following variant of Travelling Salesman Problem sometimes called Partial TSP. I'm particulary interested in the euclidian version :
Input : A set $\{x_1,\dots,x_n\}\subset \...
0
votes
1answer
60 views
Counting arrays with Euclidean distance at most 2 from a given binary array
I have a binary array like this:
$$A = [0,1,0,0,1,0]\,.$$
I'm trying to find a way to calculate how many arrays of the same length exist that have a Euclidean distance of 2 or less from this array.
...
2
votes
1answer
69 views
How to embed Pearson distance into Euclidean space
I have a lot of numerical vectors, each of dimension 1000. I would like to compare them according to their Pearson distance. This works fine but comparing all vectors to each other is quadratic time ...
1
vote
2answers
447 views
Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation
This could relate to different applications, but my application of interest is in similarity-search systems based on high-dimensional feature vectors. In these systems, since search based on ...
2
votes
1answer
61 views
Splitting a set of points in the plane evenly and sorting it
Input: A set of points P(x,y). There are two versions of it - Px, sorted by x and Py, sorted by y.
Output: The two even halves of Px, sorted by y.
The trick here is that it has to work in linear ...
1
vote
0answers
81 views
Total distance between points on a grid with time complexity lower than $O(n^2)$
I have $n$ points that form a grid with empty space and I need to find an algorithm that would calculate the total distance of those points with time complexity lower than $O(n^2)$.
An example of a ...
3
votes
1answer
97 views
Algorithm to mimimally pair up points in 3D space
Given a set of $n$ points $P$ and a set of $n$ points $Q$ in 3 dimensional space, what's the fastest algorithm to uniquely pair points in $P$ with points in $Q$ so that the sum of the square of the ...
3
votes
0answers
115 views
Is it possible to simulate/emulate non-euclidean geometry using computer graphics?
I am aware of the frequent use of "smoke and mirrors" in order to achieve the effect of non-euclidean geometry, but I was wondering it if it possible to implement spherical (sometimes called elliptic) ...
3
votes
1answer
111 views
Algorithm for shortest continuous line to join N points
I have a set of points in a 2D plane. I'm searching for an algorithm that:
Draws a continuous line passing through all the points starting from a
random point.
Optimizes for the minimum total line ...
2
votes
2answers
756 views
All nearest neighbor in a changing 2d euclidean space
I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem:
Given a 2D space with $N$ random points $p_1...p_n$, calculate the nearest neighbor of each of ...
5
votes
1answer
68 views
How to detect intersecting segments based on length of the segments
As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or ...
3
votes
1answer
89 views
Should planar Euclidean graphs be planar straight-line graphs?
An Euclidean graph, by definition is
A weighted graph in which the weights are equal to the Euclidean
lengths of the edges in a specified embedding
and a graph is called planar if
it can be ...
3
votes
2answers
1k views
How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance
I was working in my project when I was struck by the question of whether it would be necessary, or at least cautious, prevent overflow and underflow in the calculation of these two distances.
I ...
3
votes
1answer
363 views
Efficient algorithm to fulfil a set of coordinate constraints
I have a set of labelled points and a set of distance constraints between pairs of points, consisting of a lower and upper distance bound. There is definitely an arrangement of the points in 3D space ...
1
vote
1answer
2k views
Finding nearest of a list of points on Euclidian plane to a given reference point
Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$.
...
3
votes
0answers
105 views
How fast is closest pair?
I'm reading a recent paper "Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem" by Gregory Valiant on finding approximate closest pairs in $...
1
vote
0answers
16 views
Modifying the Erroneous Pairwise Distances of 4 Points to Get Coplanarity
Consider four points
$i,j,k,l$
and their pairwise Euclidiean distances
$d(ij)$
$d(ik)$
$d(il)$
$d(jk)$
$d(jl)$
$d(kl)$
Say that, we know the coordinates of the points $j$, $k$ and $l$.
However, we ...
2
votes
1answer
150 views
Can the Euclidean distance function be computed using only XOR's
The Eulidean distance function $d$ of $x$ and $y$ is given by:
$
d(x,y)=\sqrt{x^2-y^2}
$
Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. ...
10
votes
4answers
650 views
Recovering a point embedding from a graph with edges weighted by point distance
Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
