Computing the convex hull in a hammock

[[abstract]]©This paper is concerned with the problem of computing the convex hull of line-segment intersections, where all line-segment endpoints are on two vertical lines and there are no vertical line segments. We give an O(n log n) time algorithm to solve this problem, where n is the number of line segments in a hammock. By using a similar scheme, we can also solve the problem of computing the convex hull of line-segment intersections where all line-segment endpoints are on the boundary of the unit circle.[[department]]資訊工程學