Computing the smallest \(k\)-enclosing circle and related problems

DOI10.1016/0925-7721(94)90003-5zbMath0807.68102OpenAlexW2007046733MaRDI QIDQ1328752

Alon Efrat, Alon Ziv, Micha Sharir

Publication date: 3 August 1994

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(94)90003-5

zbMATH Keywords

geometric optimizationsmallest enclosing circlesmallest homothetic copy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (19)

Computing the Smallest T-Shaped Polygon Containing k Points ⋮ Efficient Speed-Up of the Smallest Enclosing Circle Algorithm ⋮ Cause I'm a genial imprecise point: outlier detection for uncertain data ⋮ On the geometry of the smallest circle enclosing a finite set of points ⋮ THE LARGEST EMPTY ANNULUS PROBLEM ⋮ Selecting distances in arrangements of hyperplanes spanned by points. ⋮ Minimum-area enclosing triangle with a fixed angle ⋮ Geometric Applications of Posets ⋮ Unnamed Item ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ On enclosing k points by a circle ⋮ Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions ⋮ Covering points with a polygon ⋮ Translating a convex polygon to contain a maximum number of points. ⋮ Optimal placement of convex polygons to maximize point containment ⋮ A near-linear algorithm for the planar segment-center problem ⋮ Offset-polygon annulus placement problems ⋮ Offset-polygon annulus placement problems ⋮ Geometric applications of posets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On enclosing k points by a circle
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Sorting in \(c \log n\) parallel steps
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• On \(k\)-sets in arrangements of curves and surfaces
• Finding k points with minimum diameter and related problems
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• New upper bounds for neighbor searching
• Optimal Point Location in a Monotone Subdivision
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Slowing down sorting networks to obtain faster sorting algorithms
• Improvements on geometric pattern matching problems
• Static and dynamic algorithms for k-point clustering problems

This page was built for publication: Computing the smallest \(k\)-enclosing circle and related problems