473,326 Members | 2,114 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Minimize the distance to a set of points

2
Hi,

I have to solve the following problem: given a set of n points, an integer d and a mxm 2D grid, find whether it is possible to place a point P such that the (Manhattan) distance between P and each point of the set is inferior to d.

Doing a DFS from each point, I think it is possible to solve it in O(nm²), but I'm asking myself how to do it in O(m²) time (ie. linear to the size of the grid).

Thanks in advance.
Oct 20 '13 #1
5 5215
Banfa
9,065 Expert Mod 8TB
I am reasonably sure that this has nothing to do with the grid size and can be done in O(n). Instead of trying each grid point and seeing if it results in the distance between P and each point of the set being inferior to d first find the point P such that the maximum distance of all the distances P and each point of the set is minimised. Then if this maximum distance is inferior to d you have a solution and if not there is no solution.

By choosing a first guess and analysing the over all distance and the distance for each axis it is possible to jump straight to the correct point almost immediately.
Oct 21 '13 #2
Nepomuk
3,112 Expert 2GB
Hi Jork and welcome to bytes.com!

I'm guessing that the algorithm you are thinking of is a brute force algorithm - it will test every point in the grid to see whether it would be a valid solution, correct? This should work of course, but my idea would be to not guess a point but rather try to calculate the position of the point clouds centre and working from there. If I'm not mistaken that should give you an O(m²) algorithm.

Oh, and Banfa: n <= m², unless you have a really weird system. ;-)
Oct 21 '13 #3
Banfa
9,065 Expert Mod 8TB
I'm well aware that n <= m² :D (Although that does assume there is not more than 1 point at any given position in the grid which isn't implicitly true).

Given that n is the size of the set of points and m is the size of the grid then I agree a brute force algorithm would have O(nm²). However If you use numerical analysis of the points then the size of the grid is irrelevant; A little experimentation suggests to me that a solution with O(n) i.e. with a lot less complexity than either O(nm²) or O(m²) is possible.

Just think about calculating the position of a clouds centre; it takes 1 scan through each point to do that, you do not even need to know the size of the grid.
Oct 21 '13 #4
jork
2
Thanks for your answers. I was indeed thinking about the bruteforce algorithm.

Computing the "center" of the point cloud looks like a good solution. However I'm not sure how to do it, since I use Manhattan distance. Does ((xmin+xmax)/2, (ymin+ymax)/2) minimize the maximum distance to every point of the cloud? Or is it a wrong idea?

Thanks in advance.
Nov 9 '13 #5
Banfa
9,065 Expert Mod 8TB
Because of the way Manhattan distance is calculated it may seem that you can consider 2 axis's separately, a change on one has on effect of the result of the other one. However in this problem we are looking to minimize the maximum journey to any point and this has some strange effects on the maths. This is because if a point has an extreme y co-ordinate but an x co-ordinate close to the centre then it is unlikely to have the largest distance to the point P because the X component of its Manhattan distance will be small.

So all that considered using ((xmin+xmax)/2, (ymin+ymax)/2) provides a good starting place but is unlikely to be the actual answer. This is because the issue is the most extreme points, the ones closest to the corners of the square bounding your points and not the points which have a single extreme co-ordinate. Also it turns out that calculating the result is not really dependent on the starting point you use and rather than wasting time finding the min and max you might as well just use the first point.

Considering a data set

Expand|Select|Wrap|Line Numbers
  1. x    y
  2. 60    34
  3. 48    76
  4. 73    75
  5. 56    52
  6. 58    46
  7. 61    56
  8. 66    66
  9. 71    55
  10. 71    35
  11. 73    40
If I choose the first point (60, 34) as my first guess and calculate distances on x and y axis (and absolute) and total their absolute values

Expand|Select|Wrap|Line Numbers
  1.       Distance
  2. x    y    total
  3. 0    0    0
  4. -12    42    54
  5. 13    41    54
  6. -4    18    22
  7. -2    12    14
  8. 1    22    23
  9. 6    32    38
  10. 11    21    32
  11. 11    1    12
  12. 13    6    19
I can see the maximum distance is currently 54. I can also see that the minimum distance is 12.

Independently for each axis (x and y) select the rows with the the largest total and a negative axis distance and the largest total and a positive axis distance. If the axis distances are all positive or all negative select the rows with the smallest and largest axis distances.

Expand|Select|Wrap|Line Numbers
  1. x axis
  2.       Distance
  3. x    y    total
  4. -12    42    54
  5. 13    41    54
  6.  
  7. y axis
  8.       Distance
  9. x    y    total
  10. -12    42    54
  11. 11    1    12
  12.  
Get the difference of the 2 totals (smallest axis value - largest axis value) divide by 2 and if the 2 values have the same sign add on the absolute value of the smallest axis value.

x - -12 < 13 and they have different signs so (54 - 54) / 2 = 0

y - 1 < 42 and they have the same sign so (54 - 12) / 2 + abs(1) = 22

Add these values onto your original guess

60 + 0 = 60, 34 + 22 = 56

Using the new point (60, 56) re-calculate your distances

Expand|Select|Wrap|Line Numbers
  1.       Distance        
  2. x    y    total
  3. 0    -22    22
  4. -12    20    32
  5. 13    19    32
  6. -4    -4    8
  7. -2    -10    12
  8. 1    0    1
  9. 6    10    16
  10. 11    -1    12
  11. 11    -21    32
  12. 13    -16    29
  13. 13    20    32

Repeat until either maximum distance stays the same (which may be with different points since there are multiple solutions) or all modifications amount to 0

Select the rows with the the largest total and a negative axis distance and the largest total and a positive axis distance.

Expand|Select|Wrap|Line Numbers
  1. x axis
  2.       Distance        
  3. x    y    total
  4. -12    20    32
  5. 13    19    32
  6.  
  7. y axis
  8.       Distance        
  9. x    y    total
  10. -12    20    32
  11. 11    -21    32
x - -12 < 13 and they have different signs so (32 - 32) / 2 = 0

y - -21 < 20 and they have different signs so (32 - 32) / 2 = 0

Therefore the P is (60, 56) and the maximum distance is 32 and you would compare that with d.


I am not sure that what I have written covers every corner case but it seems to me that it is the basis for solving this.
Nov 11 '13 #6

Sign in to post your reply or Sign up for a free account.

Similar topics

20
by: Xenophobe | last post by:
I have successfully converted the ASP code included in the following article to PHP: http://www.4guysfromrolla.com/webtech/040100-1.shtml As described the high and low latitudes and longitudes...
4
by: DellaCroce | last post by:
Does anyone here have the formula for calculating distance give two pairs of Longitude/Latitude coordinates? Please share this with me if you would. -- Greg
3
by: byteschreck | last post by:
Is it possible to change the distance from the form's border the form designer suggests when you use snaplines? I think it should be smaller.
8
by: giloosh | last post by:
how would i get the distance and angle between 2 points on the screen. For example: what is the distance between (100,50) and (250,70) what i really wanna do is see how far the current mouse...
7
by: heterodon7 | last post by:
hello, can anyone give me a clue or simple code on task: for example we have in 2D an equation fo circle: (x - 3)^2 + (y - 4)^2 = 25. now the program must return for example a 40 pairs of...
9
by: nottheartistinquestion | last post by:
As an intellectual exercise, I've implemented an STL-esque List<and List<>::Iterator. Now, I would like a signed distance between two iterators which corresponds to their relative position in the...
5
by: JD | last post by:
Hi, There are about 10+ 3-D points on the same line. I want to find the two end points from these points. The efficiency is not an issue because there are only 10 points or so. I just need a...
1
by: tiffrobe | last post by:
I'm a little lost on my program. Everything works fine except function 3. It gives out garbage numbers. Its suppose to give the distance between two points and then the area of 2 circles. ...
6
by: Tom P. | last post by:
I am writing a drawing program but I want to keep the scale down (there could end up being several hundred objects on the screen). I want to limit the points collected to a certain distance from...
7
by: sandeepshetty | last post by:
hi All, Im new to .NET ... I need your help.. I just wanted to know if their is any method or event in .NET to find the distance between two points clicked using a mouse button.... I...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.