A deterministic algorithm for the three-dimensional diameter problem

DOI10.1016/0925-7721(95)00025-9zbMath0849.68130OpenAlexW2069612526MaRDI QIDQ1917056

Otfried Schwarzkopf, Ji{ří} Matoušek

Publication date: 14 July 1996

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(95)00025-9

zbMATH Keywords

computational geometrydeterministic algorithm

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ An efficient algorithm for the three-dimensional diameter problem

Cites Work

• Diameter, width, closest line pair, and parametric searching
• On ray shooting in convex polytopes
• A deterministic view of random sampling and its use in geometry
• Cutting hyperplane arrangements
• Efficient partition trees
• Cutting hyperplanes for divide-and-conquer
• Applications of random sampling in computational geometry. II
• Approximations and optimal geometric divide-and-conquer
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms