Title:Constant Workspace Algorithms for Computing Relative Hulls in the Plane

Abstract:The constant workspace algorithms use a constant number of words in addition to the read-only input to the algorithm stored in an array. In this paper, we devise algorithms to efficiently compute relative hulls in the plane using a constant workspace. Specifically, we devise algorithms for the following three problems: \newline (i) Given two simple polygons $P$ and $Q$ with $P \subseteq Q$, compute a simple polygon $P'$ with a perimeter of minimum length such that $P \subseteq P' \subseteq Q$. \newline (ii) Given two simple polygons $P$ and $Q$ such that $Q$ does not intersect the interior of $P$ but it does intersects with the interior of the convex hull of $P$, compute a weakly simple polygon $P'$ contained in the convex hull of $P$ such that the perimeter of $P'$ is of minimum length. \newline (iii) Given a set $S$ of points located in a simple polygon $P$, compute a weakly simple polygon $P' \subseteq P$ with a perimeter of minimum length such that $P'$ contains all the points in $S$. \newline To our knowledge, no prior works devised algorithms to compute relative hulls using a constant workspace and this work is the first such attempt.