Linear Time Algorithm for 1-Center in Rd Under Convex Polyhedral Distance Function

被引：2

作者：

Das, Sandip ^{[1
]}

Nandy, Ayan ^{[1
]}

Sarvottamananda, Swami ^{[2
]}

机构：

[1] Indian Stat Inst, Kolkata 700108, India

[2] Ramakrishna Mission Vivekananda Univ, Belur Math, Howrah, WB, India

来源：

Frontiers in Algorithmics, FAW 2016 | 2016年 / 9711卷

关键词：

DIMENSION;

D O I：

10.1007/978-3-319-39817-4_5

中图分类号：

TP31 [计算机软件];

学科分类号：

081205 [计算机软件];

摘要：

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 d(P) is O(nm log(2) m). For d > 2, we present an O(3(3d2) nm(2) log(d) m) algorithm to compute 1-center of n points in R-d for convex polyhedral distance function d(P), vertical bar P vertical bar = m. Both the algorithms are linear time for fixed d and fixed polyhedron P.

引用

页码：41 / 52

页数：12

共 11 条

[1]

Minimal enclosing discs, circumcircles, and circumcenters in normed planes (Part II) [J].

Alonso, Javier ;

Martini, Horst ;

Spirova, Margarita .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2012, 45 (07) :350-369

[2]

Minimal enclosing discs, circumcircles, and circumcenters in normed planes (Part I) [J].

Alonso, Javier ;

Martini, Horst ;

Spirova, Margarita .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2012, 45 (5-6) :258-274

[3]

On linear-time deterministic algorithms for optimization problems in fixed dimension [J].

Chazelle, B ;

Matousek, J .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1996, 21 (03) :579-597

[4]

Chew L. P., 1985, Proceedings of the First Annual Symposium on Computational Geometry, SCG'85, P235, DOI [10.1145/323233.323264, DOI 10.1145/323233.323264]

[5]

ON A MULTIDIMENSIONAL SEARCH TECHNIQUE AND ITS APPLICATION TO THE EUCLIDEAN ONE-CENTER PROBLEM [J].