Finding the diameter of a set of lines

Yu-Tai Ching, D. T. Lee*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)249-255
Number of pages7
JournalPattern Recognition
Volume18
Issue number3-4
DOIs
StatePublished - 1 Jan 1985

Keywords

  • Analysis of algorithms
  • Computational geometry
  • Diameter
  • Lower bound
  • Model of computation

Cite this