## 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 language | English (US) |
---|---|

Pages (from-to) | 245-257 |

Number of pages | 13 |

Journal | Algorithmica (New York) |

Volume | 49 |

Issue number | 3 |

DOIs | |

State | Published - Nov 2007 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics