The 2-center problem in three dimensions

Published

Journal Article

© 2012 Elsevier B.V. Let P be a set of n points in R3. 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 O(β(r⁎)n2log4nloglogn) expected time; here β(r)=1/(1−r/r0)3, r⁎ is the radius of the 2-center balls of P, and r0 is the radius of the smallest enclosing ball of P. The algorithm is near quadratic as long as r⁎ is not too close to r0, 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) [2] (at the cost of making the algorithm performance depend on the center separation of the covering balls).

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Ben Avraham, R; Sharir, M

Published Date

  • August 1, 2013

Published In

Volume / Issue

  • 46 / 6

Start / End Page

  • 734 - 746

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/j.comgeo.2012.11.005

Citation Source

  • Scopus