Given any polygon, find the smallest width that it could be squeezed through. Given a shape (let's say the L-tetris-block), you put two traffic cones down and try to squeeze the shape between them without knocking over the cones. The objective is to find how close can the cones be such that the shape can still be squeezed through it?
More precisely, we of course use points instead of traffic cones. You're also allowed to slide up against those points (but not push through them). The shape is provided as an ordered list of vertex coordinates. Given that list of vertices, I want an algorithm to efficiently compute the minimum width that shape can be squeezed through.
If that's not possible, then you can make whatever concessions are necessary (e.g. assume the shape is convex, only find a bound on the width, etc.).
Also, is there a name for this minimum width?
All I know of that's similar is the Moving Sofa problem, which is definitely not the same (there's no walls in my setup, just 2 points).
In the convex case, the answer seems simple: just rotate the shape until you find the minimum cross section, and that's your answer. But the non-convex case definitely seems harder, because (e.g. for the L-tetris-block), you can keep rotating the shape to change the cross-section and squeeze it through.
 A: This is a very interesting question. As stated I believe it is very hard, since you have to worry about the entire global geometry of the shape at all times, to make sure that you don't cause intersections against the cones while trying to squeeze an unrelated part of the shape through the gap.
Put differently, your version of the problem does not obeys a monotonicity principle: it is possible for the gap between cones to be too big even though a smaller gap would work fine. (As a simple example consider sweeping a disk of small radius $r$ along a portion of the Fermat spiral. You either need the gap to be small (a big bigger than $2r$) or huge for the shape to fit through the gap.)
But I think the problem becomes tractable if you imagine that the cones are collapsible: we're allowed to continuously move the cones closer together temporarily if this is helpful, so long as we never separate the cones by more than distance $D$. Given a shape, we want to find that distance $D$.
We'll also need to assume that the shape is a (simple) polygon. We can of course bound the solution for more general curved shapes by looking at sequences of inscribing and inscribed polygons.

Problem Formulation
Even just formalizing the above problem is a bit tricky. Let's suppose our shape $P$ is a polygon with $n$ vertices $v_i$ in the plane. From $P$ we can construct an infinite polyline $\mathcal{P}$ in a covering space $\mathbb{R}^2\times \mathbb{Z}$ as follows: for every vertex $v_i$ in $P$, add vertices $(v_i, k)$ to $\mathcal{P}$ for every integer $k$; and add edges connecting $(v_i, k)$ to $(v_{i+1},k)$ for every integer $k$ and every $1 \leq i < n$, and connecting $(v_n, k)$ to $(v_1, k+1)$ for every integer $k$.
A motion of the shape through the gap can then be identified with a pair of continuous functions $\gamma, \psi: [0,1]\to \mathcal{P}$ satisfying:
\begin{align*}
\gamma(0) = \psi(0) = \gamma(1) &= (v_1, 0)\\
\psi(1) &= (v_1, 1).
\end{align*}
The curves $\gamma$ and $\psi$ encode the points on the boundary of $P$ currently inside the (shrinkable) gap between the cones. The constraints encode "passing through" the gap: by the end of the motion, one cone must have circulated around the shape while the other cone is back at the starting point without having circulated around. Note that the starting point $v_1$ is arbitrary, since we can begin by sliding both $\gamma$ and $\psi$ in lockstep along the polygon to any other desired starting point.
In what follows I will write $\gamma(t)$ and $\psi(t)$ for projection onto the first factor $\pi_1\gamma(t)$ in places where this projection is obvious (when calculating distances e.g.) to avoid clutter.
The minimum gap needed is then the minimum $D$ of
$$E(\gamma,\psi) = \min_{\gamma,\psi} \max_{t\in [0,1]} \|\gamma(t) - \psi(t)\| \quad \mathrm{s.t.}\quad \gamma(0) = \psi(0) = \gamma(1) = (v_1, 0),\ \psi(1) = (v_1, 1).$$

Candidate Distances
Suppose $D$ is the solution to our problem. This means there exist curves $\gamma,\psi$ with maximum distance $D$, which cannot be perturbed to have maximum distance $D-\epsilon$ for small $\epsilon$. This means $D$ is either:

*

*a distance between two vertices of $P$;

*a shortest distance between a vertex and edge;

as these are the only places where the distance between $\gamma$ and $\psi$ cannot be decreased by homotopy. We thus only need to check $O(n^2)$ different candidate solutions $D$.

Checking a Candidate Distance
Define a waypoint
$$W = \left[(p^1, k^1), (p^2, k^2)\right]\in \mathcal{P} \times \mathcal{P}$$
to be a pair of points where either (a) $p^1$ and $p^2$ are both vertices of $P$; (b) $p^1$ is a vertex and $p^2$ is the closest point to that vertex on an edge of $P$; or (c) vice-versa to (b).
Call two waypoints $W_i$ and $W_j$ adjacent if $p^1_i$ and $p^1_j$ are contained in a common edge on $P$, and likewise for $p^2_i$ and $p^2_j$.
Claim 1: If two curves $(\Gamma(t), \Psi(t))$ linearly interpolate two consecutive waypoints $W_1$ and $W_2$, then the maximum distance between $\Gamma$ and $\Psi$ is attained at either $W_1$ or $W_2$. This fact follows from $\Gamma$ and $\Psi$ linearly tracing along two sides of a quadrilateral.
Claim 2: Suppose $(\gamma,\psi)$ are minimizers of $E$ with minimum $D$. I claim that $\gamma$ and $\psi$ are homotopic to a discrete solution $\Gamma,\Psi$, with $E(\Gamma,\Psi) \leq D$, where $(\Gamma(t),\Psi(t))$ linearly interpolate a sequence of waypoints $\{W_1, \ldots W_k\}$ with each pair of consecutive waypoints adjacent.
This is the key lemma for solving this problem; the intuition is that for every pair of points $(\gamma(t), \psi(t))$ on the original path, you can slide that pair of points towards a waypoint without increasing the distance $\|\gamma(t)-\psi(t)\|$; discontinuities that appear during this process can be filled in with linear interpolation without increasing $E$ (per Claim 1).
The above two claims allow us to turn the problem of checking whether a solution exists for a given $D$ into a discrete graph search. Construct a graph $G$ whose vertices are all possible waypoints with distance $\leq D$; connect to waypoints by an edge if they're adjacent. $W_s = [(v_0, 0),(v_0, 0)]$ and $W_t = [(v_0, 0),(v_0, 1)]$ are both waypoints (with distance 0) and so vertices of $G$; a solution exists for the given $D$ if and only if $W_s$ and $W_t$ lie on the same connected component of $G$.

The above leads to a practical algorithm for finding $D$. First, compute the $O(n^2)$ possible values of the solution $D_i$.
For each $D_i$, construct the graph $G_i$ of waypoints as described in the previous section. Although in principle $G_i$ is infinite (since $\mathcal{P}$ is infinite), in practice one can identify $[(v_i, a+1), (v_j, b+1)]$ with $[(v_i, a), (v_j, b)]$; and then only $O(n^2)$ waypoints are reachable from $W_s$ without passing through $W_t$.
Final Algorithm
The above algorithm takes $O(n^4)$ time overall. We can reduce this to $O(n^2 \log n)$ with the following observation: instead of breadth-first search on the graph $G_i$ with all waypoints with distance greater than $D_i$ removed, we can instead run max-norm Dijkstra on a directed graph containing two copies of all waypoints (one copy contains only inbound edges; the other only outbound edges; and a directed edge connects the two copies with weight equal to the distance of that waypoint). The cost of the shortest path (under the max-norm) from $W_s$ to $W_t$ on this graph is the optimal $D$.
