Hello,
I would like to seek help about the following problem because I find it helpful in many problems in CP:
You are given a circle and a function which takes a point on the circumference of that circle and returns a real number, you know that there's one point A on that circle which gives minimum returned value of that function and one point B which gives maximum returned value of that function, and you know that the function is increasing on the paths from point A to point B (from both direction).
You don't know where are points A and B, but you know they exist. you can call the function on whichever point you want and get the value of it, one call cost O(1) time complexity, you should find points A and B within a fixed allowed small error EPS in best complexity possible (perhaps O(log(accuracy)) ?? )
assume you don't know the exact formula of that function, and it's preferable that you don't compare the value of two points which are at distance EPS from each other because in practice sometimes it's hard to choose correct EPS.
as I mentioned before this problem can exist in many problems in CP so it's useful to know how to solve it.
thanks
Let's take a random point φ0, cut a circle by it and solve the same problem for produced segment [φ0, φ0 + 2π]. Without loss of generality, assume that on this segment the function reaches its maximum first. Going from left to right, f(x) increases and reaches maximum, then decreases and at some point φ0 + θ we have f(φ0 + θ) = f(φ0), and continues decreasing. When the minimum is reached, it starts increasing back to f(φ0) = f(φ0 + 2π).
Therefore, we can use one binary search to find θ, and then do ternary search on both [φ0, φ0 + θ] and [φ0 + θ, φ0 + 2π]
Nice idea, but we need to know whether the function reaches the maximum first or minimum first before we can do binary search to find θ
We can simply determine which of the conditions holds comparing values f(φ0) and f(φ0 + ε)
Let's find B — point with maximum value.
Choose some 3 points, equally distant from each other. Let P1, P2, P3 denote them. Also, let's assume f(P1) ≤ f(P2) ≤ f(P3). Remove a segment (curve) between P1 and P2 because B isn't between them (I'm talking about a segment without P3). Maybe we removed a part with a point A but it doesn't bother us.
Now, we have a segment with endpoints P1 and P2 and some other point P3 with not smaller value. Let's ask about a new point P4 either between P1 and P3 or between P2 and P3 (choose an option with longer segment). If f(P4) > f(P3) then we can cut segment [P1, P3] out, otherwise similarly cut [P4, P2] out. This process is showed in the drawing below as green numbers 2 and 3. You may repeat it over and over. I think that it's very good in terms of precision errors.
Awesome :D
did you come up with this solution from scratch, or you know some kind of search which uses similar technique?
I tried to apply standard binary or ternary search. The latter one turned to be a good idea. One just needs to think about choosing three parts and cutting one out.
Another algorithm for basically the same problem (phrased in a slightly different context) here: http://geomalgorithms.com/a14-_extreme_pts.html
It's basically reduced to a binary search using some clever case handling.