Questions tagged [euclidean-distance]

The tag has no usage guidance.

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 131
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 ...
user avatar
  • 423
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) ...
user avatar
  • 131
3 votes
0 answers
114 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 121
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 ...
user avatar
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: ...
user avatar
  • 21
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$-...
user avatar
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 ...
user avatar
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 \...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 423
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). <...
user avatar
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 ...
user avatar
  • 11
1 vote
0 answers
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 ...
user avatar
  • 1,425
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 ...
user avatar
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) ...
user avatar
  • 137
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 ...
user avatar
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 ...
user avatar
  • 1,425
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 ...
user avatar
  • 101