Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/77
Oconvexity:computing hulls, approximations, and orientation sets
Authors  Martynchik, V.
Metelski, N. Wood, Derick 


Issue Date  199606  
Summary  We continue the investigation of computational aspects of restrictedorientation convexity (Oconvexity) in two dimensions. We introduce one notion of an Ohalfplane, for a set O of orientations, and we investigate Oconnected convexity. The Oconnected convex hull of a finite set X can be computed in time O(#X log #X + #O). The Oconnected hull is a basis for determining the Oconvex 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 minimumarea Oconnected convex outer approximation of an Opolygon with n vertices when the number r of Ohalfplanes 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  
Access 
Files in this item:
