On finding a large number of 3D points with a small diameter

DOI10.1016/J.DAM.2007.06.005zbMATH Open1132.68066OpenAlexW2068156317MaRDI QIDQ2457016FDOQ2457016

Authors: Minghui Jiang 

Publication date: 29 October 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.06.005

Recommendations

• A practical approach for computing the diameter of a point set
• Approximating the diameter of a set of points in the Euclidean space
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• scientific article; zbMATH DE number 1303550
• An efficient algorithm for the three-dimensional diameter problem

zbMATH Keywords

Clusteringcomputational geometryapproximation algorithmsuniversal coverBorsuk's conjecture

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Efficiently approximating the minimum-volume bounding box of a point set in three dimensions
• Iterated nearest neighbors and finding minimal polytopes
• Finding k points with minimum diameter and related problems
• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• Geometric applications of a randomized optimization technique
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Title not available (Why is that?)

Cited In (1)

• An efficient algorithm for the three-dimensional diameter problem

This page was built for publication: On finding a large number of 3D points with a small diameter

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