Constant Workspace Algorithms for Computing Relative Hulls in the Plane

Constant workspace algorithms use a constant number of words in addition to the read-only input to the algorithm. 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: (i) Given two simple polygons [Formula: see text] and [Formula: see text] with [Formula: see text], compute a simple polygon [Formula: see text] with a perimeter of minimum length such that [Formula: see text]. (ii) Given two simple polygons [Formula: see text] and [Formula: see text] such that [Formula: see text] does not intersect the relative interior of [Formula: see text] but it does intersect the relative interior of the convex hull of [Formula: see text], compute a weakly simple polygon [Formula: see text] with a perimeter of minimum length such that [Formula: see text], the convex hull of [Formula: see text] contains [Formula: see text], and [Formula: see text] does not intersect the relative interior of [Formula: see text]. (iii) Given a set [Formula: see text] of points located in a simple polygon [Formula: see text], compute a weakly simple polygon [Formula: see text] with a perimeter of minimum length such that [Formula: see text] and [Formula: see text] contains all the points in [Formula: see text]. To our knowledge, no prior work devised algorithms to compute relative hulls using a constant workspace, and this work is the first such attempt.