In this paper we present algorithms for computing 1-center of a set of points for convex polyhedral distance function in R~d for any d. Given polyhedral P of size m, the running time of our algorithm for computing 1-center of n points in R~2 for convex polygonal distance function dp is O(nm log~2 m). For d > 2, we present an O(3~(3d~2) nm~2 log~d m) algorithm to compute 1-center of n points in R~d for convex polyhedral distance function d_P, |P| = m. Both the algorithms are linear time for fixed d and fixed polyhedron P.
展开▼
