Questions tagged [euclidean-distance]
The euclidean-distance tag has no usage guidance.
53
questions
0
votes
1
answer
28
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 ...
- 221
0
votes
1
answer
54
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 ...
- 199
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 ...
- 11
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 ...
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. ...
- 41
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 ...
- 195
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$ ...
- 207
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 ...
- 93
0
votes
0
answers
21
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
33
views
Merge N number of euclidean distance matrices to get an overall single euclidean distance matrix
I want to find out the aggregated euclidean distance of a big dataset D comprising of x and y cordinates where the data set is divided into N sub dataset where 1st sub dataset contains 1 to kth ...
0
votes
0
answers
36
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
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
69
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
2
votes
1
answer
68
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 ...
- 23
0
votes
1
answer
47
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 ...
- 1,405
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
27
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 ...
- 249
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 ...
- 101
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$-...
3
votes
0
answers
47
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 ...
- 131
2
votes
1
answer
202
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,
...
- 121
1
vote
1
answer
38
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 $...
- 115
3
votes
0
answers
345
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
222
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
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-...
- 242
1
vote
1
answer
366
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 ...
- 113
0
votes
1
answer
107
views
Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid
There are two questions that I am trying to draw a comparison between:
...
- 235
0
votes
1
answer
720
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)...
- 51
1
vote
0
answers
28
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
143
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.
...
- 103
2
votes
1
answer
83
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 ...
- 829
1
vote
2
answers
857
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 ...
- 11
2
votes
1
answer
95
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 ...
- 23
1
vote
0
answers
204
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
1
answer
263
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
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) ...
- 131
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 ...
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
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 ...
- 153
3
votes
1
answer
120
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 ...
- 1,405
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 ...
- 41
3
votes
1
answer
468
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 ...
- 133
2
votes
1
answer
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|$.
...
- 121
3
votes
0
answers
113
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 $...
- 186