@inproceedings{89e1828188ae4e2ca43a1198c9b01d3c,

title = "Lower bounds for geometric diameter problems",

abstract = "The diameter of a set P of n points in ℝ d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure of this polytope is given, we prove that, in the worst case, deciding whether the diameter of P is smaller than 1 requires Ω(n log n) time in the algebraic computation tree model, It shows that the O(n log n) time algorithm of Ramos for computing the diameter of a point set in ℝ 3 is optimal for computing the diameter of a 3-polytope. We also give a linear time reduction from Hopcroft's problem of finding an incidence between points and lines in ℝ 2 to the diameter problem for a point set in ℝ 7.",

keywords = "Computational geometry, Convex polytope, Diameter, Hopcroft's problem, Lower bound",

author = "Herv{\'e} Fournier and Antoine Vigneron",

year = "2006",

month = jul,

day = "10",

doi = "10.1007/11682462_44",

language = "English (US)",

isbn = "354032755X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "467--478",

booktitle = "LATIN 2006",

note = "LATIN 2006: Theoretical Informatics - 7th Latin American Symposium ; Conference date: 20-03-2006 Through 24-03-2006",

}