The 2-center problem in three dimensions
type: Item
instance of: scholarly article
title: The 2-center problem in three dimensions
zbMATH Open document ID: 1273.65032
published in: Computational Geometry
publication date: 2013-04-29T00:00:00Z
review text: This paper deals with the so-called 2-center problem in \(\mathbb{R}^{3}\), i.e., the problem to find two congruent balls of minimum radius whose union covers a set of the given \(n\) points in \(\mathbb{R}^{3}\). The authors present a randomized algorithm, which is composed of a decision problem and a randomized optimization procedure. They claim that the proposed algorithm is near by quadratic unless the radius of the 2-center balls is not too close to the radius of the smallest enclosing ball. The authors also mention some open issues on this problem.
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6159340
zbMATH Keywords: 2-center problem
zbMATH Keywords: congruent balls intersection
zbMATH Keywords: randomized optimization
author: Pankaj K. Agarwal
author: Rinat Ben-Avraham
author: Micha Sharir
MaRDI profile type: Publication
full work available at URL: j.comgeo.2012.11.005
OpenAlex ID: W2206965857
cites work: Selecting distances in the plane
cites work: Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
cites work: Exact and approximation algorithms for clustering
cites work: Approximate clustering via core-sets
cites work: New algorithms for \(k\)-center and extensions
cites work: Q5501289
cites work: Geometric applications of a randomized optimization technique
cites work: More planar two-center algorithms
cites work: Cutting hyperplanes for divide-and-conquer
cites work: On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
cites work: Las Vegas algorithms for linear and integer programming when the dimension is small
cites work: Applications of random sampling in computational geometry. II
cites work: Q4344150
cites work: Batched dynamic solutions to decomposable searching problems
cites work: Q5501789
cites work: On a class of \(O(n^ 2)\) problems in computational geometry
cites work: Linear programming — Randomization and abstract frameworks
cites work: Clustering to minimize the maximum intercluster distance
cites work: Finding tailored partitions
cites work: Linear Optimization Queries
cites work: A subexponential bound for linear programming
cites work: On the complexity of some geometric problems in unbounded dimension
cites work: A near-linear algorithm for the planar 2-center problem
DOI: 10.1016/J.COMGEO.2012.11.005
description: scientific article; zbMATH DE number 6159340