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

DOI10.1007/S00453-007-9010-0MaRDI QIDQ2461545zbMATH OpenOpenAlexFDO

Authors 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 geometryConvex polytopeDiameterHopcroft's problemLower bound

Mathematics Subject Classification ID

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

Recommendations

• Lower Bounds for Geometric Diameter Problems
• scientific article; zbMATH DE number 1303550
• Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
• An optimal deterministic algorithm for computing the diameter of a three-dimensional point set
• Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions

Cites work

• 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
• Applications of random sampling in computational geometry. II
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• COMPUTING THE DIAMETER OF A POINT SET
• scientific article; zbMATH DE number 1775407 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• New lower bounds for Hopcroft's problem
• On randomized semi-algebraic test complexity
• On ray shooting in convex polytopes
• Range searching with efficient hierarchical cuttings
• Splitting a Delaunay triangulation in linear time

Cited in

(8)

• Improving bounds on the diameter of a polyhedron in high dimensions
• Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
• scientific article; zbMATH DE number 4129534 (Why is no real title available?)
• Lower Bounds for Geometric Diameter Problems
• scientific article; zbMATH DE number 1303550 (Why is no real title available?)
• Breaking the 3/2 Barrier for Unit Distances in Three Dimensions
• Computing hereditary convex structures
• An efficient algorithm for the three-dimensional diameter problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2461545)