Geometric p-Center Problems with Centers Constrained to Two Lines

被引：0

作者：

Bhattacharya, Binay ^{[1
]}

Custic, Ante ^{[2
]}

Das, Sandip ^{[3
]}

Higashikawa, Yuya ^{[4
]}

Kameda, Tsunehiko ^{[1
]}

Katoh, Naoki ^{[5
]}

机构：

[1] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC, Canada

[2] Simon Fraser Univ, Dept Math, Burnaby, BC, Canada

[3] Indian Stat Inst, Adv Comp & Microelectron Unit, Kolkata, India

[4] Chuo Univ, Dept Informat & Syst Engn, Tokyo, Japan

[5] Kwansei Univ, Sch Sci & Technol, Sanda, Hyogo, Japan

来源：

DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 | 2016年 / 9943卷

关键词：

ALGORITHMS;

D O I：

10.1007/978-3-319-48532-4_3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We first consider the weighted p-center problem, in which the centers are constrained to lie on two axis-parallel lines. Given a set of n points in the plane, which are sorted according to their x-coordinates, we show how to test in O(n log n) time if p piercing points placed on two lines, parallel to the x-axis, can pierce all the disks of different radii centered at the n given points. This leads to an O(n log(2) n) time algorithm for the weighted p-center problem. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithm runs in O(n log(2) n) time in this case as well.

引用

页码：24 / 36

页数：13

共 18 条

[11]

Hurtado F., 2000, STUDIES LOCATION ANA, P15

[12] Some variations on constrained minimum enclosing circle problem [J].

Karmakar, Arindam ;

Das, Sandip ;

Nandy, Subhas C. ;

Bhattacharya, Binay K. .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 25 (02) :176-190

[13] ON THE COMPLEXITY OF SOME COMMON GEOMETRIC LOCATION-PROBLEMS [J].

MEGIDDO, N ;

SUPOWIT, KJ .

SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :182-196

[14] LINEAR-TIME ALGORITHMS FOR LINEAR-PROGRAMMING IN R3 AND RELATED PROBLEMS [J].

MEGIDDO, N .

SIAM JOURNAL ON COMPUTING, 1983, 12 (04) :759-776

[15] THE WEIGHTED EUCLIDEAN 1-CENTER PROBLEM [J].

MEGIDDO, N .

MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (04) :498-504

[16] APPLYING PARALLEL COMPUTATION ALGORITHMS IN THE DESIGN OF SERIAL ALGORITHMS [J].

MEGIDDO, N .

JOURNAL OF THE ACM, 1983, 30 (04) :852-865

[17]

PREPARATA F.P., 1990, COMPUTATIONAL GEOMET, V3rd

[18] Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane [J].

Wang, Haitao ;

Zhang, Jingru .

ALGORITHMS AND COMPUTATION, ISAAC 2014, 2014, 8889 :3-14

← 1 2 →