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

DOI10.1007/s00453-007-9010-0zbMath1131.68110OpenAlexW2019890869MaRDI QIDQ2461545

Hervé Fournier, Antoine Vigneron

Publication date: 28 November 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9010-0

zbMATH Keywords

Computational geometryDiameterLower boundConvex polytopeHopcroft's problem

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Computing hereditary convex structures

Cites Work

• Unnamed Item
• Unnamed Item
• Range searching with efficient hierarchical cuttings
• On ray shooting in convex polytopes
• On randomized semi-algebraic test complexity
• New lower bounds for Hopcroft's problem
• Applications of random sampling in computational geometry. II
• Splitting a Delaunay triangulation in linear time
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• COMPUTING THE DIAMETER OF A POINT SET
• A practical approach for computing the diameter of a point set
• An efficient algorithm for the three-dimensional diameter problem
• An optimal deterministic algorithm for computing the diameter of a three-dimensional point set

This page was built for publication: A tight lower bound for computing the diameter of a 3D convex polytope