The 2-center problem in three dimensions

详细信息    查看全文

• 作者：Pankaj K. Agarwal^a ; ^{pankaj@cs.duke.edu} ; Rinat Ben Avraham^b ; ^{rinatba@gmail.com} ; Micha Sharir^b ; ^c ; ^{michas@post.tau.ac.il}
• 关键词：2-center ; Congruent balls intersection ; Randomized optimization
• 刊名：Computational Geometry
• 出版年：2013
• 出版时间：August, 2013
• 年：2013
• 卷：46
• 期：6
• 页码：734-746
• 全文大小：371 K

文摘

Let P be a set of n points in . The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present a randomized algorithm for computing a 2-center of P that runs in expected time; here , is the radius of the 2-center balls of P, and is the radius of the smallest enclosing ball of P. The algorithm is near quadratic as long as is not too close to , which is equivalent to the condition that the centers of the two covering balls be not too close to each other. This improves an earlier slightly super-cubic algorithm of Agarwal, Efrat, and Sharir (2000) (at the cost of making the algorithm performance depend on the center separation of the covering balls).