An efficient algorithm for the three-dimensional diameter problem

DOI10.1007/S004540010086MaRDI QIDQ5932809zbMATH OpenOpenAlexFDO

Authors Sergei Bespamyatnikh

Publication date 20 June 2001

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004540010086

zbMATH Keywords

Voronoi diagram

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• scientific article; zbMATH DE number 1303550
• A deterministic algorithm for the three-dimensional diameter problem
• An optimal deterministic algorithm for computing the diameter of a three-dimensional point set
• A tight lower bound for computing the diameter of a 3D convex polytope
• Fast algorithms for computing the diameter of a finite planar set
• scientific article; zbMATH DE number 4041267
• On finding a large number of 3D points with a small diameter
• An exact algorithm for the minimum dilation triangulation problem
• Two Algorithms for the Sum of Diameters Problem and a Related Problem
• A practical approach for computing the diameter of a point set

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• A Combinatorial Problem Connected with Differential Equations
• A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\)
• A deterministic algorithm for the three-dimensional diameter problem
• A linear time algorithm for finding all farthest neighbors in a convex polygon
• Algorithms for Reporting and Counting Geometric Intersections
• Applications of random sampling in computational geometry. II
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Computing the extreme distances between two convex polygons
• Convex hulls of finite sets of points in two and three dimensions
• Cutting hyperplanes for divide-and-conquer
• Deterministic algorithms for 3-D diameter and some 2-D lower envelopes
• Fast detection of polyhedral intersection
• Improved algorithms for discs and balls using power diagrams
• Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
• Linear combinations from power domains
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On ray shooting in convex polytopes
• Power Diagrams: Properties, Algorithms and Applications
• Product Range Spaces, Sensitive Sampling, and Derandomization
• The symmetric all-furthest-neighbor problem
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoi Diagram in the Laguerre Geometry and Its Applications

Cited in

(4)

• Computing farthest neighbors on a convex polytope.
• On finding a large number of 3D points with a small diameter
• A tight lower bound for computing the diameter of a 3D convex polytope
• An optimal deterministic algorithm for computing the diameter of a three-dimensional point set

This page was built for publication: An efficient algorithm for the three-dimensional diameter problem

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