suraniap's blog

Shortest distance out of convex area
By suraniap, history, 15 months ago, In English

Find shortest distance out of a convex area.

We have our initial starting coordinates sx, sy. We're given an API that we can call which for x and y floats returns a bool which represents if the specific point is inside the area. (def uber_has_surge(x:float, y:float) -> bool)

Find the shortest distance out of the surge pricing area in a minimum number of API calls. (assume interactive)

I thought about trying to call with 4 directions and have a circle which represents max distance that might be the answer. The problem is that this is still brute force.

Another idea would be to find a boundary point, and then do binary search on polar coordinates, but I don't understand exactly how that might work?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please define the problem more clearly? I assume you mean the shortest distance from $$$(sx,sy)$$$ to $$$(ex,ey)$$$, when both points are in some common convex area. Then, the answer needs basically $$$0$$$ queries, basically those two points can just be connected with one straight line segment, or else the set is not convex.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your understanding is correct, but we do not know (ex, ey), the convex area is unknown, we just know that we are inside (i.e. we do not have any other coordinates apart from starting point, find shortest path out in a minimal number of API calls)

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by suraniap (previous revision, new revision, compare).

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you want an exact or nearly-exact answer, there isn't an efficient solution. For instance, consider a circle centered on s with a tiny segment removed. The shortest path will be to the center of the segment's chord. There is no guaranteed way to find the chord besides checking a large number of points.

However, notice that the difference in radius between the center of the chord and the circle is very small. This can be used to make a somewhat efficient approximation.

In general, assume WLOG $$$s$$$ is the origin and suppose you have two points on the boundary separated by angle $$$0 < \theta < \pi$$$ with distances $$$r_1$$$ and $$$r_2$$$ from the origin. Further assume WLOG that the first point is on the positive x-axis and the second point is above the x-axis. The two points are $$$\left(r_1, 0\right)$$$ and $$$\left(r_2 \cos \theta, r_2 \sin \theta \right)$$$, so the line segment between them is the image of $$$\left[0, 1\right]$$$ under $$$t \mapsto \left(\left(1-t\right)r_1 + t r_2 \cos \theta, t r_2 \sin \theta \right)$$$.

By convexity, any point between these two must lie on or outside this line segment. The squared distance of the line segment to the origin is given by:

$$$\begin{align}\left(\left(1-t\right)r_1 + t r_2 \cos \theta\right)^2 + \left(t r_2 \sin \theta\right)^2 &= \left(1-t\right)^2 r_1^2 + 2 t\left(1-t\right) r_1 r_2 \cos \theta + t^2 r_2^2 \cos^2 \theta + t^2 r_2^2 \sin^2 \theta \\ &= r_1^2 - 2 t r_1^2 + t^2 r_1^2 + 2 t r_1 r_2 \cos \theta - 2 t^2 r_1 r_2 \cos \theta + t^2 r_2^2 \\ &= \left(r_1^2 + r_2^2 - 2 r_1 r_2 \cos \theta \right) t^2 + 2 r_1 \left(r_2 \cos \theta - r_1\right)t + r_1^2\end{align}$$$

Since the squared distance is quadratic in $$$t$$$, this means the minimum squared distance is either $$$r_1^2$$$, $$$r_2^2$$$, or $$$r_1^2 - \frac{4 r_1^2 \left(r_2 \cos \theta - r_1\right)^2}{4 \left(r_1^2 + r_2^2 - 2 r_1 r_2 \cos \theta\right)} = \frac{r_1^4 + r_1^2 r_2^2 - 2 r_1^3 r_2 \cos \theta - r_1^4 + 2 r_1^3 r_2 \cos \theta - r_1^2 r_2^2 \cos^2 \theta}{r_1^2 + r_2^2 - 2 r_1 r_2 \cos \theta} = \frac{r_1^2 r_2^2 \sin^2 \theta}{r_1^2 + r_2^2 - 2 r_1 r_2 \cos \theta}$$$. Notice that by the law of cosines, the denominator is just the squared distance between the two points. This last squared distance occurs at $$$t = \frac{r_1 \left(r_1 - r_2 \cos \theta\right) t}{r_1^2 + r_2^2 - 2 r_1 r_2 \cos \theta}$$$; if that is not in $$$\left[0, 1\right]$$$ then the the interval's minimum distance is achieved at one of the points.

This yields a solution: first, find the distance to the boundary in three directions separated by 120 degrees using some sort of exponential search. Then, for each pair $$$a, c$$$ of adjacent points on the boundary, find the minimum distance from $$$s$$$ to the line segment connecting them. If this is not within an acceptable tolerance of the minimum distance to the $$$a$$$ or $$$c$$$, add a point $$$b$$$ between $$$a$$$ and $$$c$$$ using binary search and recursively consider the pairs $$$a, b$$$ and $$$b, c$$$. Optimizing the order in which you consider points and how you binary search for new points' distances to $$$s$$$ and optimizing where you place $$$b$$$, among other things, may improve this by at least a constant factor.

→ Reply