HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/77
Title: O-convexity:computing hulls, approximations, and orientation sets
Authors: Martynchik, V.
Metelski, N.
Wood, Derick
Issue Date: Jun-1996
Series/Report no.: Computer Science Technical Report ; HKUST-CS96-23
Abstract: 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.
URI: http://hdl.handle.net/1783.1/77
Appears in Collections:CSE Technical Reports

Files in This Item:

File Description SizeFormat
tr9623.pdf223KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.