Reconstructing a Polyhedron between Polygons in Parallel Slices

Given two $n$-vertex polygons, $P=(p_1,\dots ,p_n)$ lying in the $xy$-plane at $z=0$, and $P^{\mathrm{\prime }}=(p_1^{\mathrm{\prime }},\dots ,p_n^{\mathrm{\prime }})$ lying in the $xy$-plane at $z=1$, a banded surface is a triangulated surface homeomorphic to an annulus connecting $P$ and $P^{\mathrm{\prime }}$ such that the triangulation’s edge set contains vertex disjoint paths ${\pi }_i$ connecting $p_i$ to $p_i^{\mathrm{\prime }}$ for all $i=1,\dots ,n$. The surface then consists of bands, where the $i$th band goes between ${\pi }_i$ and ${\pi }_{i+1}$. We give a polynomial-time algorithm to find a banded surface without Steiner points if one exists. We explore connections between banded surfaces and linear morphs, where time in the morph corresponds to the $z$ direction. In particular, we show that if $P$ and $P^{\mathrm{\prime }}$ are convex and the linear morph from $P$ to $P^{\mathrm{\prime }}$ (which moves the $i$th vertex on a straight line from $p_i$ to $p_i^{\mathrm{\prime }}$) remains planar at all times, then there is a banded surface without Steiner points.