Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Linear Time Algorithm for 1-Center in \(\mathfrak {R}^d\) Under Convex Polyhedral Distance Function
verfasst von : Sandip Das, Ayan Nandy, Swami Sarvottamananda
Erschienen in: Frontiers in Algorithmics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.