A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope |
| |
Authors: | Hervé Fournier Antoine Vigneron |
| |
Affiliation: | (1) Laboratoire PRiSM, Université de Versailles Saint-Quentin-en-Yvelines, 45 avenue des états-Unis, 78035 Versailles cedex, France;(2) INRA, UR341 Mathématiques et Informatique Appliquées, Domaine de Vilvert, 78352 Jouy-en-Josas cedex, France |
| |
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. |
| |
Keywords: | Computational geometry Lower bound Diameter Convex polytope Hopcroft’ s problem |
本文献已被 SpringerLink 等数据库收录! |
|