Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with 2 values $(x_i, y_i)$. We want to count the size of set $y$ such that $y$ includes all the points in the grid that are on equal distance from all of the $x$ points.

By distance I mean Manhattan distance.

  • 1
    $\begingroup$ What's your question? What have you tried? What algorithms have you already considered? Are you able to come up with any algorithm at all, regardless of running time? What's wrong with the obvious algorithm: try each grid point, calculate its distance to each of the $x$ points, and see if it belongs in the output? What's wrong with the next-most-obvious algorithm, of looping over the distance $d$ and for each $d$, enumerating all points that are at distance $d$ from all of the $x$ points? $\endgroup$ – D.W. Mar 12 '18 at 21:17
  • $\begingroup$ For the first obvious algorithm, the wrong is that it is very slow $O(NM)$ if $N = M = 30000$. The second algorithm has the same complexity, if i'm getting it correct. $\endgroup$ – someone12321 Mar 13 '18 at 6:32
  • $\begingroup$ Please define "very slow". Have you actually measured it? How do you plan to evaluate answers? What quantitative metric do you plan to use? Doing $10 \times 30000^2$ distance computations sounds like something that can be done in fractions of a second. No, the second algorithm might be faster. My other questions still stand. I suggest you spend some more time trying out the obvious approaches, see if they meet your needs, and if you rejected them, use that to figure out what exactly your requirements are, and edit the question to provide additional context. $\endgroup$ – D.W. Mar 13 '18 at 16:22
  • $\begingroup$ On standard computer being able to process $10^8$ computations per second, $10\cdot 30000^2$ is going to take 90 seconds. I need algorithm that will finish it under 1 second. I tried many of those searches but they all work in the same complexity, so we need to find some different search. $\endgroup$ – someone12321 Mar 14 '18 at 6:13

Hint: First solve the problem for the case where x=2. Try working through a few examples: draw a picture of the grid, work out the solution (plot the points that are at equal distance from both input points), see what pattern you can spot, and use that to find a solution for the case where x=2. I think you'll discover something fascinating.

Once you can solve it for x=2, you are almost done! Think about how you might expand that to x=3.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.