Questions tagged [euclidean-distance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
44 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 ...
Meni's user avatar
  • 103
1 vote
1 answer
81 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 $...
chausies's user avatar
  • 532
0 votes
0 answers
7 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 ...
Julius H.'s user avatar
  • 123
1 vote
1 answer
39 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 ...
Bazza's user avatar
  • 13
1 vote
1 answer
40 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 ...
Achille G's user avatar
  • 113
0 votes
1 answer
186 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 ...
disguisedtoast's user avatar
0 votes
1 answer
211 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 ...
MathCurious's user avatar
0 votes
1 answer
62 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 ...
user3779002's user avatar
1 vote
1 answer
13 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 ...
Bob's user avatar
  • 11
1 vote
1 answer
48 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 ...
user12878817821's user avatar
4 votes
2 answers
151 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. ...
user147260's user avatar
1 vote
1 answer
30 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 ...
iago-lito's user avatar
  • 195
1 vote
1 answer
53 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$ ...
Dmitry's user avatar
  • 315
3 votes
1 answer
62 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 ...
magnetlion's user avatar
4 votes
0 answers
68 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 ...
TarsEndurance's user avatar
0 votes
0 answers
69 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 ...
FlubberBeer's user avatar
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 ...
aru_bdd's user avatar
  • 21
2 votes
0 answers
83 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 ...
shunyo's user avatar
  • 121
1 vote
0 answers
73 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 ...
Sam's user avatar
  • 11
1 vote
0 answers
47 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 ...
3nondatur's user avatar
  • 457
2 votes
1 answer
124 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 ...
Ignirion's user avatar
0 votes
1 answer
65 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 ...
padawan's user avatar
  • 1,425
2 votes
0 answers
46 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 ...
Paul Accisano's user avatar
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: ...
Erik's user avatar
  • 21
0 votes
1 answer
44 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 ...
user2994783's user avatar
0 votes
2 answers
182 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 ...
Fred E's user avatar
  • 101
2 votes
0 answers
151 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$-...
Michael Dunne's user avatar
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 ...
jdowdell's user avatar
  • 131
2 votes
1 answer
231 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, ...
Jacco's user avatar
  • 121
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 $...
Diogo Santos's user avatar
3 votes
0 answers
415 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 ...
Celelibi's user avatar
  • 443
3 votes
0 answers
289 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 ...
Strabonio's user avatar
  • 131
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-...
theantomc's user avatar
  • 262
1 vote
1 answer
444 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 ...
alehresmann's user avatar
0 votes
1 answer
143 views

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

There are two questions that I am trying to draw a comparison between: ...
user248884's user avatar
0 votes
1 answer
776 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)...
PeppaPig's user avatar
1 vote
0 answers
33 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). <...
shdotcom's user avatar
0 votes
0 answers
172 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 ...
Al rl's user avatar
  • 101
2 votes
0 answers
28 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 \...
Mathieu Mari's user avatar
0 votes
1 answer
117 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. ...
Jarom's user avatar
  • 103
2 votes
1 answer
87 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 ...
Simd's user avatar
  • 890
1 vote
2 answers
920 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 ...
Sohrab's user avatar
  • 11
2 votes
1 answer
132 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 ...
SUBmarinoff's user avatar
1 vote
0 answers
285 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 ...
Mike's user avatar
  • 11
3 votes
1 answer
427 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 ...
Alecto Irene Perez's user avatar
3 votes
0 answers
164 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) ...
Joe Carr's user avatar
  • 131
3 votes
1 answer
133 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 ...
John Papastergiou's user avatar
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 ...
Rahkiin's user avatar
  • 23
5 votes
1 answer
80 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 ...
Picarus's user avatar
  • 153
3 votes
1 answer
134 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 ...
padawan's user avatar
  • 1,425