Advertisement
Published in:
2016 | OriginalPaper | Chapter
Linear Time Algorithm for 1-Center in \(\mathfrak {R}^d\) Under Convex Polyhedral Distance Function
Authors : Sandip Das, Ayan Nandy, Swami Sarvottamananda
Published in: Frontiers in Algorithmics
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
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.