Please use this identifier to cite or link to this item:

O-convexity:computing hulls, approximations, and orientation sets

Authors Martynchik, V.
Metelski, N.
Wood, Derick
Issue Date 1996-06
Summary 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(#X log #X + #O). The O-connected hull is a basis for determining the O-convex hull of a finite set X for a finite set O of orientations in time O(#X#O log #X). 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^2r+ #O). 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 assume that O is sorted.
Language English
Format Technical report
Files in this item:
File Description Size Format
tr9623.pdf 228659 B Adobe PDF