Finding k points with minimum diameter and related problems

DOI10.1016/0196-6774(91)90022-QzbMath0715.68082MaRDI QIDQ3201788

Naoki Katoh, Subhash Suri, Hiroshi Imai, Alok Aggarwal

Publication date: 1991

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

optimization; diameter; Voronoi diagrams

Mathematics Subject Classification ID

68T10: Pattern recognition, speech recognition

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

Related Items

Differential approximation of NP-hard problems with equal size feasible solutions, Computing the Smallest T-Shaped Polygon Containing k Points, Square and Rectangle Covering with Outliers, On enclosing k points by a circle, An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane, Region-restricted clustering for geographic data mining, Algorithms for optimal outlier removal, Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation, Finding minimum area \(k\)-gons, Finding the \(k\) smallest spanning trees, Iterated nearest neighbors and finding minimal polytopes, Computing the smallest \(k\)-enclosing circle and related problems, Cluster analysis and mathematical programming, Compact location problems, On geometric optimization with few violated constraints, On finding a large number of 3D points with a small diameter, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS, Minimum area polygons with two reflex angles enclosingkPoints