The 2-center problem in three dimensions

DOI10.1145/1810959.1810974MaRDI QIDQ5405866zbMATH OpenOpenAlexFDO

Authors Rinat Ben-Avraham, Pankaj K. Agarwal, Micha Sharir

Publication date 3 April 2014

Published in Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.2694

zbMATH Keywords

2-center problemfacility locationgeometric optimizationintersection of congruent ballsmulti-dimensional parametric searchingspherical polytopes

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Abstract: Let P be a set of n points in R^3. The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present two randomized algorithms for computing a 2-center of P. The first algorithm runs in O(n^3 log^5 n) expected time, and the second algorithm runs in O((n^2 log^5 n) /(1-r*/r_0)^3) expected time, where r* is the radius of the 2-center balls of P and r_0 is the radius of the smallest enclosing ball of P. The second algorithm is faster than the first one as long as r* is not too close to r_0, which is equivalent to the condition that the centers of the two covering balls be not too close to each other.

Recommendations

• The 2-center problem in three dimensions
• More planar two-center algorithms
• The discrete 2-center problem
• An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
• Efficient planar two-center algorithms

Cited in

(7)

• The 2-center problem in three dimensions
• On the planar two-center problem and circular hulls
• Syzygies in the two center problem
• Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls
• An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
• scientific article; zbMATH DE number 970602 (Why is no real title available?)
• Intersecting disks using two congruent disks

This page was built for publication: The 2-center problem in three dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405866)