# Tag Info

Accepted

### kd-tree stores points in inner nodes? If yes, how to search for NN?

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search: ...
• 251
Accepted

### Find k nearest neighbors on a sphere

Use the space partitioning approach to nearest neighbor search. For instance, one approach is to use a $k$-d tree on on the surface of the sphere. You can express every point on the sphere using ...
• 145k
Accepted

### Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question ...
• 80.6k

• 80.6k

### A data structure that makes finding close objects easy

Data structures designed to organize multi-dimensional data can help, for instance quad trees or, more generally, k-d-trees. It might also be possible to apply ideas from sweep-line algorithms, ...
• 71.2k

### Nearest Neighbor Search in Spherical Coordinates

Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates. I don't understand this restriction. Converting to Cartesian coordinates uses essentially ...
• 2,072
Accepted

### Nearest neighbour based on subjective human comparison - is this a thing?

Distance metric learning It sounds like you want to learn a distance metric $D(\cdot,\cdot)$ on the items. If the human tells you that A is more similar to B than to C, then you learn that \$D(A,B) &...
• 145k
Accepted

### Find nearest neighbour in a radius

The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter. While searching the K-D tree for your ...
• 12.4k

### kdtree or balltree supporting insertion/deletion

My experience comes mainly from kd-trees. I think this answers part of your question and the attached image really visualizes the problem. When you construct the kd-tree initially the tree is ...
• 200

### kdtree or balltree supporting insertion/deletion

I am not sure about BallTrees, but kd-trees definitely support deletion (see my Java implementation here). I think the reason why it is often not implemented is that it is a lot more complex and may ...
• 709
Accepted

### A nearest neighbor data structure for meshes

It suffices to store all of the triangles from all of the meshes in a nearest-neighbor data structure for triangles. Then, given a point P, find the nearest triangle, check which mesh that triangle ...
• 145k
1 vote

### Placing a point between two nearest ones

Don't add the point between the closest pair of points; add it between the endpoints of the closest edge.
• 80.6k
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 ...
1 vote

### How to efficiently compute the most isolated point?

Use any algorithm for all nearest neighbors; then you can trivially solve your problem. Such an algorithm finds, for each data point, its nearest neighbor. The most isolated point is the one whose ...
• 145k

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