Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [euclidean-distance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
243 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 vote
0 answers
24 views

Clustering 2D points with flavour

Problem Description I have two sets of 2D points with flavours: Noisy points $$p_i = (x_i, y_i, f_i) : p_i \in N : |N|\approx 10^8 $$ and true points $$p_{t_i} = (x_{t_i}, y_{t_i}, f_{t_i}) : p_{t_i} \...
0 votes
1 answer
81 views

Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space

Given a closed polygon defined in the 2D Euclidean plane. My objective is to determine the point within this polygon that is furthest away from its boundary. In other words, I want to find the point ...
1 vote
1 answer
157 views

Finding shortest path between two points in a polygon whose vertices are given?

A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
0 votes
0 answers
12 views

Does T5 or another embedding embed every possible length tokenization?

I’m curious about an embedding technique where every possible “tokenization” of a text gets an embedding - not just individuals words, but every single 2-gram, 3-gram, and n-gram. Does this exist? Or ...
1 vote
1 answer
45 views

Efficient ways to sort pairwise distances for set of points in Euclidean space?

Consider a Euclidean space $\mathbb{R}^d$. Consider $ X \subset \mathbb{R}^d$ where $X$ is a finite set with $|X|=n$. Consider the set of line segments $\{xy | x,y \in X\}$ . I have a process $Z$ that ...
0 votes
1 answer
74 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 vote
1 answer
44 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 ...
0 votes
1 answer
326 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 ...
0 votes
1 answer
65 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 ...
1 vote
1 answer
14 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 ...
1 vote
1 answer
54 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
184 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 vote
1 answer
35 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 ...
1 vote
1 answer
58 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$ ...
3 votes
1 answer
66 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 ...
4 votes
0 answers
72 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
74 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 ...
10 votes
4 answers
1k 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 ...
2 votes
0 answers
145 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
0 answers
85 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 ...
1 vote
0 answers
75 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
0 answers
53 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 ...
3 votes
0 answers
51 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
142 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 ...
3 votes
1 answer
2k 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-...
2 votes
0 answers
52 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
0 answers
35 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
1 answer
49 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
2 answers
214 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
0 answers
152 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
237 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
1 answer
41 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
0 answers
446 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 ...
3 votes
0 answers
333 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 ...
0 votes
1 answer
154 views

Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid

There are two questions that I am trying to draw a comparison between: ...
1 vote
1 answer
466 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
1 answer
784 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
0 answers
34 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
0 answers
179 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
0 answers
31 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
1 answer
122 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. ...
3 votes
1 answer
137 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
1 answer
90 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 ...
3 votes
1 answer
464 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 ...
1 vote
2 answers
936 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
1 answer
147 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
0 answers
301 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
0 answers
170 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) ...
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 ...