Finding the diameter of a set of lines

摘要

Consider a set of n straight lines in the plane. The diameter of the set of lines is the distance between the farthest pair of intersection points determined by the set of lines. In this paper we present an O(n log n) algorithm for computing the diameter and show that the algorithm is optimal to within a constant factor under the algebraic computation tree model of Ben-Or.