Abstract:
Metrics or distance functions generalizing the Euclidean metric (and even Lp-metrics) have been used in Computational Geometry long ago; for example, convex distance functions appeared in the first Symposium on Computational geometry [2]. Very recently Das et al. [5] studied the 1-center problem under a convex polyhedral distance function where the unit ball of the distance function is a convex polytope. In this paper we develop algorithms for the 2-center problem under a convex polyhedral distance function in Rd, d = 2, 3. We show that the 2-center can be computed in O(n log m) time for the plane and in O(nm log n) time for d = 3. We show that the problem of for computing the 2-center in R3 has an Ω(n log n) lower bound.(Paper by Sergey Bereg)