Questions tagged [euclidean-distance]
The euclidean-distance tag has no usage guidance.
42
questions
2
votes
0answers
141 views
Optimal Item Locations given Traversal Paths
I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations.
Additionally, I have a ...
2
votes
0answers
51 views
Mahalanobis distance of point to plane algorithm
I am trying to understand the Mahalanobis distance of a point from the plane given by this paper. The algorithm is given below:
Calculate covariance of point $S_{uu}$
Apply a whitening transform to ...
0
votes
0answers
13 views
What's the best way to combine multiple A* searches?
I have a graph that looks like this
The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
1
vote
0answers
61 views
Can we make at most 3 comparisons in the closest points algorithm instead of 7?
Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be ...
1
vote
0answers
28 views
Show that the local feature size is Lipschitz continuous
In class we defined "local features size" $\rho$ as follows:
Let $C$ be a smooth closed curve in the plane, and let $x$ be a
point of $C$. The local feature size $\rho(x)$ of $x$ is the ...
2
votes
1answer
39 views
Why is it hard to show that the euclidean Steiner tree problem is in NP?
I read that for the euclidean Steiner tree problem it is known that it is NP-hard, but not known whether it is in NP or not. [Wikipedia]
Shouldn't the euclidean version obviously be in NP since the ...
0
votes
1answer
32 views
Scaling down a set of points into a smaller area
A visibility graph $G(P) = (V,E)$ of a set $P = \{p_1, \dots, p_n\}$ of points is defined as follows.
Each vertex $u \in V$ corresponds to a point $p_u \in P$.
There exists an edge $uv \in E$ if, and ...
2
votes
0answers
32 views
Finding multiple paths through a grid such that every grid square is equally used
Setup
Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
2
votes
0answers
28 views
Efficient parameterization of low vertex count polygons
I'm trying to design a method to represent polygons as vectors. There are many ways to do this, but I have a few goals and I'm not sure what representation is best to fulfil these. The objectives are:
...
0
votes
1answer
22 views
Computing the minimum distance between each pain of points
I am trying to read an algorithm for computing minimum distance between each pair of points from the book: Algorithm Design
Algorithm Design
It considers the points in a line. If the points are in ...
0
votes
2answers
88 views
Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case
Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can ...
2
votes
0answers
143 views
“Loneliest point” algorithm
Problem:
I'm looking for an algorithm to find the maximal Euclidean distance between points in a set $R$ and another set $S \subseteq R$.
Specifically, given a finite set of points $S$ in $n$-...
3
votes
0answers
40 views
Distance from high dimensional convex hull to target point T
I have a set S of high dimensional points in Euclidean space, with convex hull H (not known); and some target point T in that space not in or on H.
Rather than worry about calculating both H and the ...
2
votes
1answer
120 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
33 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 $...
3
votes
0answers
296 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
194 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 ...
3
votes
1answer
738 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
318 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
72 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
577 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
24 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
116 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
22 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
91 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
76 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
763 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
80 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
133 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
187 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
140 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
123 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
2k 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
70 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
107 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
2k 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
441 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 ...
2
votes
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
110 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
230 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
793 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 ...
