Advertisement
Published in:
2016 | OriginalPaper | Chapter
On the 2-Center Problem Under Convex Polyhedral Distance Function
Author : Sergey Bereg
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Metrics or distance functions generalizing the Euclidean metric (and even \(L_p\)-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 \(\mathbb {R}^d,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 \(\mathbb {R}^3\) has an \(\varOmega (n\log n)\) lower bound.