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.

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 ...