THE SLAB DIVIDING APPROACH TO SOLVE THE EUCLIDEAN P-CENTER PROBLEM

被引：58

作者：

HWANG, RZ

LEE, RCT

CHANG, RC

机构：

[1] CHINESE ACAD SCI, SHANGHAI, PEOPLES R CHINA

[2] NATL CHIAO TUNG UNIV, INST COMP SCI, HSINCHU, TAIWAN

来源：

ALGORITHMICA | 1993年 / 9卷 / 01期

关键词：

COMPUTATIONAL GEOMETRY; NP-COMPLETENESS;

D O I：

10.1007/BF01185335

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given n demand points on the plane, the Euclidean P-Center problem is to find P supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, is 0(n2P-1 . log n). In this paper, we present an algorithm with time complexity 0(n0(square-root P))).

引用

页码：1 / 22

页数：22

共 13 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[3] MULTIDIMENSIONAL DIVIDE-AND-CONQUER [J].

BENTLEY, JL .

COMMUNICATIONS OF THE ACM, 1980, 23 (04) :214-229

[4] ON A MODIFIED ONE-CENTER MODEL [J].

DREZNER, Z .

MANAGEMENT SCIENCE, 1981, 27 (07) :848-851

[5]

DREZNER Z, 1984, J OPER RES SOC, V35, P741, DOI 10.2307/2581980

[6]

DREZNER Z, 1987, NAV RES LOG, V34, P229, DOI 10.1002/1520-6750(198704)34:2<229::AID-NAV3220340207>3.0.CO

[7]

2-1

[8]

Helly Eduard, 1923, JAHRESBER DTSCH MATH, V32, P175

[9]

Horowitz E., 1978, FUNDAMENTALS COMPUTE

[10] APPLICATIONS OF A PLANAR SEPARATOR THEOREM [J].

LIPTON, RJ ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :615-627

← 1 2 →