Efficient Way To Compute Points Where Convolution Equals Zero

Question

I want to model the following procedure. Given a shape $L\subseteq\mathbf{R}^2$ (imagine e.g. a letter) and another (could be convex if it makes life easier) shape $K\subseteq\mathbf{R}^2$, I want to compute $\{p\in\mathbf{R}^2: ((1-1_L)*1_K)(p)=0\}$ (in terms of convolution) or $\{p\in\mathbf{R}^2:\forall k\in K:p+k\in L\}$ in an alternative formulation, e.g. all points $p$ such that $K$ centered at $p$ fits into $L$. What strategies do I have to perform this at high resolution?

One idea I had was that for every shape $K$ there should exist a set of points $\{d_i\}_i$ such that if I already know that $p+d_i$ is in my set for all $i$ then $p$ must be in the set as well. E.g. if $K$ is the ball with radius $1$ then $\{(0,1),(1,0),(0,-1),(-1,0)\}$ would be such a set. Using this I could create some grid where I compute the function first and from there deduce some values, then maybe proceed with a finer grained grid?

Answer 1

I'll describe one way to solve this, with a sweepline algorithm, which I think works. The approach is a bit complex, though it is fully general, should be efficient, and gives the exact answer.

My approach is inspired by the Bentley-Ottmann algorithm, so if this answer is hard to follow, it might be worth reading and understanding that first.

I will assume that the shapes $L,K$ are the interior of polygons, and $K$ is convex. I assume we know the vertices of these polygons. An edge of a polygon is a line segment between two adjacent vertices (i.e., a line segment on the perimeter). Let $p=(p_x,p_y)$, i.e., $p_x$ is the $x$-coordinate of $p$ and $p_y$ is the $y$-coordinate of $p$.

We'll use the following fact about containment:

Fact: If there are no intersections between the edges of $K,L$, and one vertex of $K$ is inside $L$, then $K \subseteq L$, i.e., $K$ is contained in $L$.

(See e.g. https://stackoverflow.com/a/4833823/781723 and https://stackoverflow.com/a/52827803/781723.)

Let $v$ be a vertex of $K$ (any vertex; say the leftmost one). Then the goal is equivalent to finding all $p$ such that there is no intersection between the edges of $K+p$ and $L$, and such that $v+p$ is inside $L$. To find this set of $p$, we'll use a sweepline algorithm.

At any time step in the execution of the sweepline algorithm, we'll have a vertical sweepline at some particular $x$-coordinate, namely at $p_x$. The goal will be to find all values of $p_y$ such that $K+(p_x,p_y)$ is contained in $L$, i.e., such that there is no intersection between the edges of $K+(p_x,p_y)$ and $L$, and such that $v+(p_x,p_y)$ is inside $L$. So let's take a moment to figure out how to achieve that goal. Then, we'll need to sweep the value of $p_x$ in an increasing way, so I'll need to discuss how to achieve that.

Given a fixed value of $p_x$, here is how we can find all satisfactory $p_y$. Consider any edge $e$ of $K$ and any edge $f$ of $L$. Then the set of $p_y$ such that $e+(p_x,p_y)$ does not intersect $f$ is a union of two intervals and is easy to compute. Thus, the set of $p_y$ such that $e+(p_x,p_y)$ does not intersect any edge of $L$ is a union of intervals and is also easy to compute. Similarly, the set of $p_y$ such that $v+(p_x,p_y)$ is inside $L$ is another union of intervals that is also to compute. We can intersect those two sets, to get the set of satisfactory values of $p_y$, represented as a union of disjoint intervals.

Notice that in this set of values of $p_y$, the endpoint of each interval corresponds to a critical value of $p_y$ that causes an intersection between $e+(p_x,p_y)$ and $f$, for some edges $e,f$ of $K,L$ respectively.

What if we increase $p_x$ a tiny bit? What will that do to the endpoint of one of those sets? It'll change the critical value of $p_y$ a tiny bit, and it is easy to compute this change if you know the corresponding $e,f$. In particular, in some neighborhood of this $p_x$, there is a linear relationship between $p_x$ and this interval endpoint (this critical value of $p_y$). You can also compute the region of validity of this linear relationship (its end corresponds to the $x$-coordinate of the endpoints of $e,f$, which is the first to the right and the first to the left). Each end of the region of validity is an "event" (i.e., value of $p_x$ where things change).

This lets you build a sweepline algorithm. For a fixed $p_x$, you can compute the set of valid values of $p_y$, and a similar relationship that holds in the neighborhood (region of validity). Between each pair of adjacent events (i.e., values of $p_x$), you can express the set of valid values of $p_y$ as a disjoint union of intervals whose endpoints are linear functions of $p_x$.

In this way, we can build up a data structure that represents the valid pairs $(p_x,p_y)$. Essentially, it is a union of a bunch of trapezoids, where each trapezoid has a left and right edge that is vertical and aligns with an "event", and where the top and bottom are sloping based on the linear relationship between $p_x$ and $p_y$ that holds in that region of validity.

That's a lot of words, and it sounds pretty complex. I apologize that I didn't have time to draw pictures to try to make this clearer. I hope this is helpful nonetheless. I imagine there be corner cases to work out that I have glossed over, based on special cases (e.g., where $e,f$ intersect not at a single point but are parallel, and so on).