Finding k points with minimum diameter and related problems
From MaRDI portal
Publication:3201788
DOI10.1016/0196-6774(91)90022-QzbMath0715.68082OpenAlexW2046227217MaRDI QIDQ3201788
Alok Aggarwal, Naoki Katoh, Subhash Suri, Hiroshi Imai
Publication date: 1991
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(91)90022-q
Pattern recognition, speech recognition (68T10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Computing the Smallest T-Shaped Polygon Containing k Points ⋮ Iterated nearest neighbors and finding minimal polytopes ⋮ Computing the smallest \(k\)-enclosing circle and related problems ⋮ Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Computing a minimum-width square or rectangular annulus with outliers ⋮ Cause I'm a genial imprecise point: outlier detection for uncertain data ⋮ Enclosing \(k\) points in the smallest axis parallel rectangle ⋮ Finding the k smallest spanning trees ⋮ Approximation and inapproximability results for maximum clique of disc graphs in high dimensions ⋮ Static and dynamic algorithms for k-point clustering problems ⋮ On geometric optimization with few violated constraints ⋮ Cluster analysis and mathematical programming ⋮ Selecting a subset of diverse points based on the squared Euclidean distance ⋮ Square and Rectangle Covering with Outliers ⋮ Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center ⋮ Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space ⋮ Compact location problems ⋮ Covering points by disjoint boxes with outliers ⋮ Compact location problems with budget and communication constraints ⋮ Maximizing single attribute diversity in group selection ⋮ Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster ⋮ Complexity and approximability of certain bicriteria location problems ⋮ Solving some vector subset problems by Voronoi diagrams ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Computing optimal islands ⋮ Covering points with convex sets of minimum size ⋮ Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters ⋮ Polynomial-Time Approximation Scheme for a Problem of Searching for the Largest Subset with the Constraint on Quadratic Variation ⋮ QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS ⋮ On finding a large number of 3D points with a small diameter ⋮ Finding minimum area \(k\)-gons ⋮ On enclosing k points by a circle ⋮ Largest and smallest area triangles on imprecise points ⋮ An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane ⋮ Finding the \(k\) smallest spanning trees ⋮ Minimum area polygons with two reflex angles enclosingkPoints ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Placing Two Axis-Parallel Squares to Maximize the Number of Enclosed Points ⋮ Region-restricted clustering for geographic data mining ⋮ Covering Points with Convex Sets of Minimum Size ⋮ Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence ⋮ Unnamed Item ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ Computing a Minimum-Width Square or Rectangular Annulus with Outliers ⋮ NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Smallest k-enclosing rectangle revisited ⋮ Algorithms for optimal outlier removal ⋮ Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation ⋮ Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space ⋮ Complexity and approximation of the smallest \(k\)-enclosing ball problem ⋮ Approximation and complexity of the capacitated geometric median problem
This page was built for publication: Finding k points with minimum diameter and related problems
