# Inclusion probability of irregularly shaped polygon

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?

• In what sense is a circle a polygon? – 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.