Reconstructing a Polyhedron between Polygons in Parallel Slices

Abstract

Given two $n$-vertex polygons, $P=(p_1,\dots ,p_n)$ lying in the $xy$-plane at $z=0$, and $P^{\prime }=(p_1^{\prime },\dots ,p_n^{\prime })$ lying in the $xy$-plane at $z=1$, a banded surface is a triangulated surface homeomorphic to an annulus connecting $P$ and $P^{\prime }$ such that the triangulation's edge set contains vertex disjoint paths ${\pi }_i$ connecting $p_i$ to $p_i^{\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^{\prime }$ are convex and the linear morph from $P$ to $P^{\prime }$ (which moves the $i$th vertex on a straight line from $p_i$ to $p_i^{\prime }$) remains planar at all times, then there is a banded surface without Steiner points.

preliminary version appeared in the Canadian Conference on Computational Geometry (CCCG) 2019