O-Convexity Computing Hulls Approximations and Orientation Sets
V. N. Martynchik, Nikolai N. Metelski, Derick Wood · 1996
We continue the investigation of computational aspects of restricted-orientation convexity (O-convexity) in two dimensions. We introduce one notion of an O-halfplane, for a set O of orientations, and we investigate O-connected convexity. The O-connected convex hull of a finite set X can be computed in time O(jX j log jX j + jOj). The O-connected hull is a basis for determining the O-convex hull of a finite set X and a finite set O of orientations in time O(jXjjOj log jXj). We also consider two new problems. First, we give an algorithm to determine a minimum-area O-connected convex outer approximation of an O-polygon with n vertices when the number r of O-halfplanes forming the approximation is given. The approximation can be determined in time O(n 2 r+ j O j). Second, we give an algorithm to find the largest orientation set for a simple polygon. This problem can be solved in time O(n log n), where n is the number of vertices of the polygon. For each of these complexity bounds we a...