# Finding the optimal point among several weighted points in linear time

I'm trying to find the best position in a set of points where each point p has a weight w. I need to take into account the distance between each point and the weight of the points, the point with the lowest weight to distance value is the solution. (A more detailed description can be found a bit further down the page.)

I've thought about implementing some sort of a graph algorithm to solve this but there are not many graph algorithms that run in linear time, I really don't understand how I'm supposed to solve it with that time complexity. Could anyone please give me a hint on what sort of an algorithm I should implement here?

Problem

Superman can see through objects made of different materials using x-ray vision. However, the amount of energy he requires varies according to the opacity of the material, e.g., steel requires more energy than wood. In addition, the farther away, the more energy he must use.

Along a straight coastline, n bunkers made of different materials have been built. Each bunker is placed at the one-dimensional coordinate position p2, p1,...,pn, with pi < pi + 1, along the coastline so you can assume that the bunkers are given in the order they appear along the coastline. Assume further that you have wi, 1 <= i <= n, the amount of energy ( a non-zero, positive value) superman needs to see into the i’th bunker if he stands next to it.

Find an algorithm that computes the point s along the coastline for which superman can exert the minimum amount of energy to see into all the bunkers, i.e., s is the position for which

max{ | s - pi | + wi }

1<=i<=n

is minimized. Your algorithm should take linear time.

• Sounds like you want the centroid or something similar to that? – G. Bach Nov 21 '17 at 13:29
• Hint: Find all local minima. There should be $O(n)$ of these, so you can just try out all of them. – Yuval Filmus Nov 21 '17 at 14:42
• What's the context where you encountered this? Please cite the source of the material, and make sure to provide proper attribution for all quoted material. – D.W. Nov 22 '17 at 2:26