Lower bounds for geometric diameter problems

Hervé Fournier*, Antoine Vigneron

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish (US)
Title of host publicationLATIN 2006
Subtitle of host publicationTheoretical Informatics - 7th Latin American Symposium, Proceedings
Pages467-478
Number of pages12
DOIs
StatePublished - Jul 10 2006
EventLATIN 2006: Theoretical Informatics - 7th Latin American Symposium - Valdivia, Chile
Duration: Mar 20 2006Mar 24 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3887 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherLATIN 2006: Theoretical Informatics - 7th Latin American Symposium
CountryChile
CityValdivia
Period03/20/0603/24/06

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Lower bounds for geometric diameter problems'. Together they form a unique fingerprint.

Cite this