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^*

^*此作品的通信作者

數據科學與工程研究所

研究成果: Article › 同行評審

16 引文斯高帕斯（Scopus）

摘要

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.

原文	English
頁（從 - 到）	249-255
頁數	7
期刊	Pattern Recognition
卷	18
發行號	3-4
DOIs	https://doi.org/10.1016/0031-3203(85)90050-0
出版狀態	Published - 1985

存取文件

10.1016/0031-3203(85)90050-0

其它文件與鏈接

Link to publication in Scopus

引用此

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

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

language = "English",

volume = "18",

pages = "249--255",

journal = "Pattern Recognition",

issn = "0031-3203",

publisher = "Elsevier Ltd",

number = "3-4",

}

TY - JOUR

T1 - Finding the diameter of a set of lines

AU - Ching, Yu-Tai

AU - Lee, D. T.

PY - 1985

Y1 - 1985

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 - https://www.scopus.com/pages/publications/0021942650

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

摘要

存取文件

其它文件與鏈接

指紋

引用此