I have two shapes, one is a circle, let's call it Circle A, and another irregularly shaped Polygon B. A will always have a greater area than B. Both of these polygons exist inside an area S.

My task is to compute the inclusion probability of Polygon B in a random sample, where inclusion is defined as Polygon B being entirely inside of Circle A (the circle).

My assumption is that the inclusion probability of Polygon B is the area of another Polygon C, which equates to the area in which Circle A can be placed so that it can enclose Polygon B divided by the total area of S.

If this assumption is correct, then computing Polygon C seems computationally intensive.

Is there an efficient method for finding Polygon C?

  • $\begingroup$ In what sense is a circle a polygon? $\endgroup$ – David Eppstein Feb 6 '18 at 3:57

The first thing to notice is that an $n$-vertex polygon polygon $B$ is inside circle $A$ if and only if all of the vertices of $B$ are inside $A$. (1)

So the solution to your problem is exactly the area of $n$ arbitrary intersecting circles, each of radius $r$ and centered at a vertex of $B$. (You then divide by $S$ to get the final probability). There's an interesting blog about this problem here which includes some heuristic solutions which may be sufficient for your use case.

From a theoretical point of view, the furthest-point Voronoi diagram gives us a good starting point. Let's look at a point $p$ inside a cell of the furthest-point Voronoi diagram. We want to know if the circle $A$ centered at $p$ contains $B$. By the above, this happens if and only if all vertices of $B$ are within distance $r$ of $p$. Now, since we're inside a cell of the furthest-point Voronoi diagram, we can just test whether or not $p$ is within distance $r$ of that furthest point.

In particular, the area we want within a given Voronoi cell is the intersection of that Voronoi cell with a single circle of radius $r$. This can be easily calculated in time linear in the number of edges of the cell. Since the furthest-point Voronoi diagram has $O(n)$ cells with $O(n)$ total edges, this takes $O(n)$ time in total.

Then the total running time is dominated by the time to calculate the furthest-point Voronoi diagram, which is $O(n \log n)$. A similar strategy gives you an explicit region $C$ in the same amount of time.

(1): The "only if" direction is obvious. To see the "if" direction, we can first note that by convexity if all vertices of $B$ are inside $A$, then all edges of $B$ must be as well. The same argument then extends to all interior points of $B$ since they must lie on a line between two vertices or edges.

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