On enclosing k points by a circle

DOI10.1016/0020-0190(94)00190-AzbMath0875.68895OpenAlexW2073335364WikidataQ127960420 ScholiaQ127960420MaRDI QIDQ674185

Ji{ří} Matoušek

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00190-a

zbMATH Keywords

ClusteringComputational geometryComputational complexityParametric searchRandomized algorithmSmallest enclosing circle

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Computing the Smallest T-Shaped Polygon Containing k Points ⋮ Computing the smallest \(k\)-enclosing circle and related problems ⋮ Efficiently approximating color-spanning balls ⋮ On geometric optimization with few violated constraints ⋮ A branch-and-bound method for the minimum \(k\)-enclosing ball problem ⋮ The approximation algorithms for a class of multiple-choice problem ⋮ Minimum-area enclosing triangle with a fixed angle ⋮ Unnamed Item ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS ⋮ Optimal consensus set for digital flake hyperspheres in \(n\)D ⋮ GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON ⋮ Simple algorithms for partial point set pattern matching under rigid motion ⋮ Region-restricted clustering for geographic data mining

Cites Work

• Unnamed Item
• Diameter, width, closest line pair, and parametric searching
• Randomized optimal algorithm for slope selection
• Computing the smallest \(k\)-enclosing circle and related problems
• Applications of random sampling in computational geometry. II
• On geometric optimization with few violated constraints
• Finding k points with minimum diameter and related problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Static and Dynamic Algorithms for k-Point Clustering Problems
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION