Questions tagged [euclidean-distance]
The euclidean-distance tag has no usage guidance.
54
questions
1
vote
1
answer
30
views
Find the placement of gates on 2D points that minimizes the total distance of all paths to be made
Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path.
For example,
Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E'
Gate 'B' will have to go to 'D'
Gate 'C' will ...
D.W.♦
- 143k
0
votes
1
answer
53
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 ...
CommunityBot
- 1
0
votes
1
answer
47
views
Efficient Method for Distance Comparison in Euclidean Space
I have a vector of 2D Euclidean coordinates, and I need to find out if two or more points are within a distance threshold.
The naive approach is to compare each point with every other point, but I am ...
- 1
0
votes
1
answer
29
views
Finding smallest triangle to fit all points
I'm supposed to find an algorithm that, given a bunch of points on the Euclidean plane, I have to return the tightest (smallest) origin centered upright equilateral triangle that fits all the given ...
- 4,460
0
votes
1
answer
55
views
Cosine distance in a space, and cheating?
I read an example of using cosine distance in RGB space, and it pointed out that (eg.) dark red and light red have a cosine distance (CD) of zero because CD only gives you the angle between vectors ...
- 4,460
1
vote
1
answer
11
views
Finding overlapping time under distance condition
I have a set of records (2 or more for each person) on multiple peoples locations (latitude and longitude) with timestamps.
each record has: person ID, latitude, longitude, timeStamp.
for each 2 ...
D.W.♦
- 143k
1
vote
1
answer
22
views
Locality Sensitive Hashing for Sets
Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer ...
D.W.♦
- 143k
4
votes
2
answers
91
views
Given a vector of points, what is the fastest algorithm to find all pairs of points at a distance of 1?
Given a vector of points (on the 2D plane), what is the fastest algorithm to find all pairs of points at a distance of 1?
Of course, I could use the $O(N^2)$ algorithm to check all pairs of points. ...
- 1,396
1
vote
1
answer
25
views
Efficient intersection detection between disks with identical radius
I have a set of $N$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose ...
D.W.♦
- 143k
1
vote
1
answer
32
views
Embedding from $L^\infty$ space to $L^2$ space
I have a set $X$ of $n$ points in a $poly(n)$-dimensional $L^\infty$ space. Does there exist a way to map the points into $poly(n)$-dimensional $L^2$ space so that the distances between points in $X$ ...
- 270k
3
votes
1
answer
57
views
A heuristic for finding the vector that is maximally distant from a set of vectors
I have two sets of vectors: A and B. I want to find the vector Bi in set ...
- 13.3k
0
votes
0
answers
22
views
Is it possible to approximate the cosine similarity by dot products?
My goal is to find an approximate way to calculate the cosine similarity by inner products.
Before the question look at the image below taken from Improved Asymmetric Locality Sensitive Hashing (ALSH) ...
- 137
4
votes
0
answers
62
views
Finding the smallest distance between a point and a set of points
I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
0
votes
0
answers
37
views
Euclidean space vs metric space in density clustering algorithms
I'm trying to find out if these algorithm still work if i replace the Euclidean space with metric space defined on the input point set. But i'm having some trouble figuring it out for some of them. I ...
- 27
10
votes
4
answers
894
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 ...
- 706
2
votes
0
answers
143
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 ...
- 21
2
votes
0
answers
71
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 ...
- 121
1
vote
0
answers
67
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 ...
- 11
1
vote
0
answers
32
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 ...
- 423
3
votes
0
answers
49
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
1
answer
76
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 ...
- 2,209
3
votes
1
answer
1k
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-...
- 270k
2
votes
0
answers
37
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 ...
- 151
2
votes
0
answers
31
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:
...
- 21
0
votes
1
answer
28
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 ...
D.W.♦
- 143k
0
votes
2
answers
122
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 ...
- 689
2
votes
0
answers
149
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$-...
2
votes
1
answer
205
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,635
1
vote
1
answer
39
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 $...
- 689
3
votes
0
answers
348
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 ...
- 423
2
votes
0
answers
223
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 ...
- 21
0
votes
1
answer
112
views
Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid
There are two questions that I am trying to draw a comparison between:
...
CommunityBot
- 1
1
vote
1
answer
370
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 ...
- 589
0
votes
1
answer
727
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)...
- 554
1
vote
0
answers
29
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).
<...
- 11
0
votes
0
answers
144
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 ...
- 101
2
votes
0
answers
25
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 \...
- 366
0
votes
1
answer
102
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.
...
- 80.4k
3
votes
1
answer
129
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 ...
- 80.4k
2
votes
1
answer
84
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 ...
D.W.♦
- 143k
3
votes
1
answer
272
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 ...
CommunityBot
- 1
1
vote
2
answers
861
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 ...
- 25.4k
2
votes
1
answer
96
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 ...
- 270k
1
vote
0
answers
206
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 ...
- 11
3
votes
0
answers
146
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) ...
D.W.♦
- 143k
2
votes
2
answers
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 ...
- 23
3
votes
2
answers
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 ...
CommunityBot
- 1
5
votes
1
answer
76
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 ...
- 1,304
3
votes
1
answer
121
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 ...
- 270k
3
votes
1
answer
470
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 ...
D.W.♦
- 143k