A near-linear algorithm for the planar 2-center problem

DOI10.1007/PL00009311zbMath0878.68131OpenAlexW2001145975MaRDI QIDQ1364134

Micha Sharir

Publication date: 24 August 1997

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00009311

zbMATH Keywords

two-center problem

Mathematics Subject Classification ID

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

Related Items (31)

Improved algorithms for the bichromatic two-center problem for pairs of points ⋮ Efficiently approximating color-spanning balls ⋮ The mixed center location problem ⋮ The Discrete and Mixed Minimax 2-Center Problem ⋮ An efficient algorithm for the proximity connected two center problem ⋮ A local search approximation algorithm for \(k\)-means clustering ⋮ Streaming with minimum space: an algorithm for covering by two congruent balls ⋮ The Mixed Center Location Problem ⋮ Efficient algorithms for computing one or two discrete centers hitting a set of line segments ⋮ The discrete and mixed minimax 2-center problems ⋮ The two-center problem of uncertain points on a real line ⋮ Efficient \(k\)-center algorithms for planar points in convex position ⋮ The 2-center problem in three dimensions ⋮ BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES ⋮ Base station placement on boundary of a convex polygon ⋮ VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION ⋮ Minimum-sum dipolar spanning tree in \(\mathbb R^3\) ⋮ OBNOXIOUS FACILITY LOCATION: COMPLETE SERVICE WITH MINIMAL HARM ⋮ Efficient planar two-center algorithms ⋮ Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares ⋮ A simple linear algorithm for computing rectilinear 3-centers ⋮ Parametric search: three new applications ⋮ Minimum perimeter-sum partitions in the plane ⋮ Covering convex polygons by two congruent disks ⋮ Intersecting disks using two congruent disks ⋮ Intersecting disks using two congruent disks ⋮ Pose estimation and object identification using complex algebraic representations ⋮ A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM ⋮ Covering convex polygons by two congruent disks ⋮ On the planar two-center problem and circular hulls ⋮ COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET

This page was built for publication: A near-linear algorithm for the planar 2-center problem