Stack Overflow
Stack Overflow

Questions tagged [closest-points]

107 questions
31
votes
2 answers

Nearest Neighbor Search: Python

I have a 2 dimensional array: MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0], [6588253.79, 1933602.89, 212.66, 0, 0], etc...) The first two elements MyArray[0] and MyArray[1] are the X and Y coordinates of…
Dlinet
  • 1,193
  • 3
  • 15
  • 22
23
votes
5 answers

Closest group of 3 points

Is there a known, efficient algorithm for finding the closest group of three points in a cloud? This is similar to the closest pair of points problem but I am looking for three points instead of two. Edit The definition of "closest" will affect the…
finnw
  • 47,861
  • 24
  • 143
  • 221
14
votes
6 answers

How to align two unequal sized timeseries numpy array?

I have two numpy arrays containing timeseries (unix timestamps). I want to find pairs of timestamps (1 from each array) whose difference is within a threshold. For achieving this, I need to align two of the time series data into two arrays, such…
Dexters
  • 2,419
  • 6
  • 37
  • 57
8
votes
4 answers

Closest Pair Implemetation Python

I am trying to implement the closest pair problem in Python using divide and conquer, everything seems to work fine except that in some input cases, there is a wrong answer. My code is as follows: def closestSplitPair(Px,Py,d): X =…
maverick93
  • 143
  • 1
  • 4
  • 13
8
votes
1 answer

Boost Library and closest points

I can find the distance between a point MyPoint and a polygon MyPolygon with double dist = boost::geometry::distance(MyPoint, MyPolygon) obviously the actual closest point on MyPolygon has to be computed somewhere. Is there an easy way to get that…
user3049681
  • 397
  • 4
  • 12
7
votes
1 answer

Closest Pair of Points in 3+ Dimensions (Divide and Conquer)

I am struggling to wrap my head around how the divide and conquer algorithm works for dimensions greater than 2, specifically how to find the closest pair of points between two sub-problems. I know that I need to only consider points within a…
DonGato
  • 93
  • 1
  • 4
6
votes
1 answer

Closest pair of points algorithm

I am trying to implement a simpler version of this algorithm but which works better than the quadratic algorithm. My idea basically is to sort the points by only x coordinate and try to solve it from there. Once I sort my array of points by x…
Paul
  • 1,059
  • 4
  • 17
  • 23
6
votes
2 answers

Closest pair of points algorithm variation

I know this may be a duplicate, but it seems like a variation on the 'Closest pair of Points' algorithm. Given a Set of N points (x, y) in the unit square and a distance d, find all pair of points such that the distance between them is at most…
Fernando
  • 7,785
  • 6
  • 49
  • 81
6
votes
2 answers

Haskell to find the distance between the two closest points

Given a list of points in a two dimensional space, you want to perform a function in Haskell to find the distance between the two closest points. example: Input: project [(1,5), (3,4), (2,8), (-1,2), (-8.6), (7.0), (1.5), (5.5), (4.8),…
franvergara66
  • 10,524
  • 20
  • 59
  • 101
5
votes
4 answers

Algorithm, closest point between list elements

I have n ordered lists of unequal size (where I do not know beforehand how many lists there are going to be). I need to find the minimum average distance between one element in each list. For example given n=3 for three lists: a = [14, 22, 36, 48] b…
D.A.
  • 140
  • 1
  • 12
5
votes
2 answers

Closest pair algorithm for comparing points from 2 different arrays

I would like to compare the points from one array to the points from another array and find the closest pair. Till now whatever I have come across is with a single array. I do not want to compare the points from the same array. The brute force…
Lawrence
  • 427
  • 5
  • 15
5
votes
5 answers

Closest pair of points across a line

I have two sets of 2D points, separated from each other by a line in the plane. I'd like to efficiently find the pair of points, consisting of one point from each set, with the minimum distance between them. There's a really convenient looking paper…
Sneftel
  • 40,271
  • 12
  • 71
  • 104
4
votes
2 answers

Finding Nearest Node for Each Node

I have 2 sets of nodes - Set A and Set B. Each set is of size 25,000. I am given a percentage (lets say 20%). I need to find the minimum distance such that 20% of the nodes in Set A are within that distance of any node in Set B. Solution: Find the…
Evorlor
  • 7,263
  • 17
  • 70
  • 141
4
votes
1 answer

Fastest way to find n closest nodes to a given node in a directed weighted graph

Right now I'm performing Dijkstra's algorithm on the entire graph and forming a min-heap of the nodes by total distance from the origin node. I then remove the top n elements from the heap. This strikes me as seriously inefficient. Suppose I need to…
ask
  • 2,160
  • 7
  • 31
  • 42
3
votes
2 answers

Finding closest pair of points in the plane with non-distinct x-coordinates in O(nlogn)

Most of the implementations of the algorithm to find the closest pair of points in the plane that I've seen online have one of two deficiencies: either they fail to meet an O(nlogn) runtime, or they fail to accommodate the case where some points…
jmath
  • 33
  • 5
1
2 3 4 5 6 7 8