A tight lower bound for computing the diameter of a 3D convex polytope

Hervé Fournier*, Antoine Vigneron

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 Ω(nlog∈n) time in the algebraic computation tree model. It shows that the O(nlog∈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.

Original languageEnglish (US)
Pages (from-to)245-257
Number of pages13
JournalAlgorithmica (New York)
Volume49
Issue number3
DOIs
StatePublished - Nov 1 2007

Keywords

  • Computational geometry
  • Convex polytope
  • Diameter
  • Hopcroft's problem
  • Lower bound

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A tight lower bound for computing the diameter of a 3D convex polytope'. Together they form a unique fingerprint.

Cite this