Ordered stabbing of pairwise disjoint convex sets in linear time

Ordered stabbing of pairwise disjoint convex sets in linear time

0.00 Avg rating0 Votes
Article ID: iaor19912047
Country: Netherlands
Volume: 31
Issue: 2
Start Page Number: 133
End Page Number: 140
Publication Date: Apr 1991
Journal: Discrete Applied Mathematics
Authors: ,
Abstract:

Given an ordered family of n pairwise disjoint convex simple objects in the plane, the authors given an O(n) time algorithm for finding the directed line transversals of the family that intersect the objects in order. Objects are simple if they have a constant size storage description, and if the intersections and common tangents between any two objects can be found in constant time. The present O(n) time algorithm contrasts with an ¦[(nlogn) lower bound for finding a line transversal of a family of n convex simple objects in the plane.

Reviews

Required fields are marked *. Your email address will not be published.