Abstract
The diameter of a set P of n points in \({\mathbb R}^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 \({\mathbb R}^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 \({\mathbb R}^2\) to the diameter problem for a point set in \({\mathbb R}^7\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P., Matoušek, J., Suri, S.: Farthest neighbors, maximum spanning trees and related problems in higher dimensions. Computational Geometry: Theory and Applications 1(4), 189–201 (1992)
Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 80–86 (1983)
Bespamyatnikh, S.: An efficient algorithm for the three-dimensional diameter problem. Discrete and Computational Geometry 25(2), 235–255 (2000)
Bürgisser, P., Clausen, M., Shokrollahi, M.: Algebraic Complexity Theory. Springer, Heidelberg (1997)
Chan, T.: Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. International Journal of Computational Geometry and Applications 12(1–2), 67–85 (2002)
Chazelle, B., Devillers, O., Hurtado, F., Mora, M., Sacristán, V., Teillaud, M.: Splitting a delaunay triangulation in linear time. Algorithmica 34(1), 39–46 (2002)
Cheong, O., Shin, C., Vigneron, A.: Computing farthest neighbors on a convex polytope. Theoretical Computer Science 296(1), 47–58 (2003)
Clarkson, K., Shor, P.: Applications of random sampling in computational geometry, II. Discrete and Computational Geometry 4, 387–421 (1989)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (2000)
Erickson, J.: On the relative complexities of some geometric problems. In: Proceedings of the 7th Canadian Conference on Computational Geometry, pp. 85–90 (1995)
Erickson, J.: New lower bounds for Hopcroft’s problem. Discrete and Computational Geometry 16, 389–418 (1996)
Har-Peled, S.: A practical approach for computing the diameter of a point set. In: Proceedings of the Seventeenth Annual Symposium on Computational Geometry, June 3–5, pp. 177–186. ACM Press, New York (2001)
Malandain, G., Boissonnat, J.-D.: Computing the diameter of a point set. International Journal of Computational Geometry and Applications 12(6), 489–510 (2002)
Matoušek, J.: Range searching with efficient hierarchical cuttings. Discrete and Computational Geometry 10(2), 157–182 (1993)
Matoušek, J., Schwarzkopf, O.: On ray shooting in convex polytopes. Discrete and Computational Geometry 10(2), 215–232 (1993)
Preparata, F., Shamos, I.: Computational geometry: An introduction, 2nd edn. Texts and Monographs in Computer Science. Springer, New York (1985)
Ramos, E.: An optimal deterministic algorithm for computing the diameter of a three-dimensional point set. Discrete and Computational Geometry 26, 233–244 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fournier, H., Vigneron, A. (2006). Lower Bounds for Geometric Diameter Problems. In: Correa, J.R., Hevia, A., Kiwi, M. (eds) LATIN 2006: Theoretical Informatics. LATIN 2006. Lecture Notes in Computer Science, vol 3887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11682462_44
Download citation
DOI: https://doi.org/10.1007/11682462_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32755-4
Online ISBN: 978-3-540-32756-1
eBook Packages: Computer ScienceComputer Science (R0)