Linear Time Algorithm for 1-Center in Rd Under Convex Polyhedral Distance Function
Linear Time Algorithm for 1-Center in Rd Under Convex Polyhedral Distance Function
复制标题
凸多面体距离函数下Rd中1中心的线性时间算法
DOI：
10.1007/978-3-319-39817-4_5
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
Swami Sarvottamananda
中科院分区：
文献类型：
--
作者：
Sandip Das;Ayan Nandy;Swami Sarvottamananda
本文给出了计算任意d的凸多面体距离函数集上n个点的1中心的算法.给定m的多面体P，计算凸多面体距离函数(DP)上n个点的1中心的算法的运行时间为O(Nmlog2m).对于d>；2，对于凸多面体距离函数dP，(|P|=m)，我们给出了一个计算(mathfrak{R}^d)中n个点的1-中心的O(3^{3d^2}nm^2\log^dm)算法.这两种算法对于固定d和固定多面体P都是线性时间。
In this paper we present algorithms for computing 1-center of a set of points for convex polyhedral distance function in \(\mathfrak {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 \(\mathfrak {R}^2\) for convex polygonal distance function \(d_P\) 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 \(\mathfrak {R}^d\) for convex polyhedral distance function \(d_P\), \(|P|=m\). Both the algorithms are linear time for fixed d and fixed polyhedron P.