Finding the diameter of a set of lines

Yu-Tai Ching; D. T. Lee

doi:10.1016/0031-3203(85)90050-0

Finding the diameter of a set of lines

Yu-Tai Ching, D. T. Lee^*

^*Corresponding author for this work

Institute of Data Science and Engineering

Research output: Contribution to journal › Article › peer-review

16 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 language	English
Pages (from-to)	249-255
Number of pages	7
Journal	Pattern Recognition
Volume	18
Issue number	3-4
DOIs	https://doi.org/10.1016/0031-3203(85)90050-0
State	Published - 1 Jan 1985

Keywords

Analysis of algorithms
Computational geometry
Diameter
Lower bound
Model of computation

Access to Document

10.1016/0031-3203(85)90050-0

Cite this

@article{2c19579d09034c3cb80caae01360a214,

title = "Finding the diameter of a set of lines",

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.",

keywords = "Analysis of algorithms, Computational geometry, Diameter, Lower bound, Model of computation",

author = "Yu-Tai Ching and Lee, {D. T.}",

year = "1985",

month = jan,

day = "1",

doi = "10.1016/0031-3203(85)90050-0",

language = "English",

volume = "18",

pages = "249--255",

journal = "Pattern Recognition",

issn = "0031-3203",

publisher = "Elsevier Limited",

number = "3-4",

}

TY - JOUR

T1 - Finding the diameter of a set of lines

AU - Ching, Yu-Tai

AU - Lee, D. T.

PY - 1985/1/1

Y1 - 1985/1/1

N2 - 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.

AB - 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.

KW - Analysis of algorithms

KW - Computational geometry

KW - Diameter

KW - Lower bound

KW - Model of computation

UR - http://www.scopus.com/inward/record.url?scp=0021942650&partnerID=8YFLogxK

U2 - 10.1016/0031-3203(85)90050-0

DO - 10.1016/0031-3203(85)90050-0

M3 - Article

AN - SCOPUS:0021942650

SN - 0031-3203

VL - 18

SP - 249

EP - 255

JO - Pattern Recognition

JF - Pattern Recognition

IS - 3-4

ER -

Finding the diameter of a set of lines

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this