Optimal computation of finitely oriented convex hulls (Q1820432)

For a simple finitely oriented polygon four versions of the concept ''convex hull'' are defined. The aim of the paper is to give optimal algorithms to find them. Let F be a finite set of orientations and let an F-polygon be a polygon whose edges have only orientations from F. Further call a polygon F-convex if the intersection of the polygon with any F- line (i.e. a line whose orientation stems from F) is either empty or a line segment. Then the authors derive results like the following. If the orientations in F are sorted then testing a simple F-polygon for F- convexity can be achieved in \(\Theta (n+| F|)\) time and \(\Theta\) (n) space, n being the number of edges of \(\Pi\). The authors also prove a result which gives bounds for time and space during which each of the four hulls can be found optimally.