# Questions tagged [euclidean-distance]

The tag has no usage guidance.

49 questions
Filter by
Sorted by
Tagged with
22 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$ ...
49 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 ...
20 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) ...
54 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 ...
20 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 ...
12 views

### Cosine vs Manhattan to measure Text Similarity after doc2vec Embedding

I have a list of documents and made doc2vec embedding to them using BERT model so now they are stored as vectors in Elasticsearch database. I want to apply semantic search given a query from the user ...
21 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 ...
142 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 ...
56 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 ...
14 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 ...
63 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 ...
29 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 ...
47 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 ...
37 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 ...
34 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 ...
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: ...
23 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 ...
94 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 ...
145 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$-...
44 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 ...
147 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, ...
33 views

26 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). <...
127 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 ...
22 views

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 ...
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$. ...