4 votes
Accepted

Should planar Euclidean graphs be planar straight-line graphs?

Fáry's theorem states that every planar graph can be drawn in such a way that its edges are (non-crossing) straight lines. Hence every planar graph is a planar straight-line graph. However, this ...
Yuval Filmus's user avatar
3 votes
Accepted

Embedding from $L^\infty$ space to $L^2$ space

The answer is unfortunately negative in general, by combining the following two well-known facts: Every metric space on $n$ points embeds isometrically into $(n-1)$-dimensional $L^\infty$. Embedding ...
Yuval Filmus's user avatar
3 votes
Accepted

How to detect intersecting segments based on length of the segments

First assume that you know where $A,B,C,D$ are. In this case, you can write $D$ uniquely in the form $\alpha_A A + \alpha_B B + \alpha_C C$, with $\alpha_A + \alpha_B + \alpha_C = 1$. The tuple $(\...
Louis's user avatar
  • 2,926
3 votes
Accepted

Why is it hard to show that the euclidean Steiner tree problem is in NP?

I'm guessing the difficulty lies in the fact that euclidean distance is involved, and we don't know if comparing sums of integrer square roots is in NP. The problem is the following: for integers $a_1,...
Tassle's user avatar
  • 2,522
3 votes
Accepted

Finding Euclidean Minimum Spanning Tree

If you're asking this question because you want something easier to implement than a Delaunay triangulation algorithm you're most likely out of luck. You should also specify in what space you're ...
oerpli's user avatar
  • 574
2 votes
Accepted

Splitting a set of points in the plane evenly and sorting it

This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points ...
Yuval Filmus's user avatar
2 votes
Accepted

Counting arrays with Euclidean distance at most 2 from a given binary array

Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units. Since your arrays are binary, $$(A_i-B_i)^2 = \begin{...
David Richerby's user avatar
2 votes
Accepted

How to embed Pearson distance into Euclidean space

Yes. Normalize the vectors, then use the Euclidean ($L_2$) distance. In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector $$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$ where $\mu=(v_1+...
D.W.'s user avatar
  • 159k
2 votes

Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern ...
TilmannZ's user avatar
  • 764
2 votes

How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance

That is a long solved problem. First, if you are using double precision floating point numbers in IEEE754 format (which is most common), that's what extended precision was invented for. Even in the ...
gnasher729's user avatar
2 votes
Accepted

Find the placement of gates on 2D points that minimizes the total distance of all paths to be made

Based on the reformulation of your problem from Bernardo Subercaseaux, your problem is NP-hard (as John L explains), so you should not expect an algorithm that will be efficient in the worst case. ...
D.W.'s user avatar
  • 159k
2 votes
Accepted

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

A better solution could be as follows: Create a min heap over $n^2$ line segments. Take the top element of the heap, check if it satisfies condition $C$. If it does not satisfy it, pop it out. If it ...
Inuyasha Yagami's user avatar
2 votes

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

The graph that you defined is known as visibility graph. You can find a $O(n^2 \log n)$ algorithm here. There are other better algorithms stated in the first link. Note the algorithms are for the ...
Inuyasha Yagami's user avatar
2 votes
Accepted

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

The medial axis is the set of points in the interior of the shape that has two closest points on the boundary. Intuitively, the largest "incircle" in a polygon must touch the boundary at at ...
Pseudonym's user avatar
  • 22.1k
1 vote

A heuristic for finding the vector that is maximally distant from a set of vectors

Just to answer with some ideas. If you have too many dimensions, you can use the Johnson–Lindenstrauss lemma to reduce the dimensions while keeping distances approximately the same (some $\epsilon$ ...
Pål GD's user avatar
  • 16.1k
1 vote

Finding overlapping time under distance condition

Sort the records for each person, by increasing timestamp. Given a pair of people, you can merge the sorted list of records for each of those two people, and then do a linear scan over that sorted ...
D.W.'s user avatar
  • 159k
1 vote

Given a vector of points, what is the fastest algorithm to find all pairs of points at a distance of 1?

The problem can be regarded as a special case of incidence reporting problem with $N$ unit circles and $N$ points in the plane. If the number of unit circles is $m$, then this problem can be solved in ...
pcpthm's user avatar
  • 2,348
1 vote

Given a vector of points, what is the fastest algorithm to find all pairs of points at a distance of 1?

You may use a Well-Separated Pairs Decomposition (WSPD). This is a hierarchical decomposition, where at each level, you split the points into two parts, each of them a certain distance from the sphere ...
Discrete lizard's user avatar
  • 8,248
1 vote
Accepted

Efficient intersection detection between disks with identical radius

Use any standard data structure / algorithm for nearest neighbor search. In particular, you are interested in the fixed-radius nearest neighbor problem, for which there are many algorithms.
D.W.'s user avatar
  • 159k
1 vote

Scaling down a set of points into a smaller area

The following procedure achieves your requirements: Step 1: Find the smallest circle that encloses all points. (There are standard algorithms for this.) Step 2: Compute the area of that circle. Step ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Computing the minimum distance between each pain of points

Suppose the points are $[4,1,10,11]$. The distance from the starting point (whether you interpret that as $4$ or $1$) to each other point does not give you the nearest pair of points. In this ...
D.W.'s user avatar
  • 159k
1 vote

Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

The best I can come up with is to compute the centroid of each object and store the centroids in a nearest-neighbor data structure; to find the matches for a test object $T$, look up its centroid in ...
D.W.'s user avatar
  • 159k
1 vote

Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

Suppose $G$ is a weighted graph, and $T_{OPT}$ is the optimal route you seek. For clarity: $T_{OPT}$ is a path that connects all vertices, such that for any other path $P$ that connects all vertices,...
lox's user avatar
  • 1,669
1 vote
Accepted

Closest k points - performance on large lists

I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points. ...
TilmannZ's user avatar
  • 764
1 vote
Accepted

expected pairwise square euclidean distance between points

Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $[0,1]^d$. That is, $x_1,\ldots,x_d,y_1,\ldots,y_d$ are all uniform random samples of the uniform ...
Yuval Filmus's user avatar
1 vote
Accepted

In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific ...
Reinstate Monica's user avatar
1 vote
Accepted

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

It is nice that you try to draw a comparison between two similar situations. However, it looks like you are driving too fast to stay on the right road. Henceforth I will be moving somewhat slowly so ...
John L.'s user avatar
  • 39k
1 vote

Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation

The asymptotic complexity for the worst case is the same. Actually, the constant factors will be quite close together on a typical modern processor - if you don't calculate the execution time ...
gnasher729's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible