The discrete 2-center problem

被引：30

作者：

Agarwal, PK

Sharir, M

Welzl, E

机构：

[1] Duke Univ, Dept Comp Sci, Ctr Geometr Comp, Durham, NC 27708 USA

[2] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel

[3] NYU, Courant Inst Math Sci, New York, NY 10012 USA

[4] ETH Zurich, Inst Theoret Informat, CH-8092 Zurich, Switzerland

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1998年 / 20卷 / 03期

关键词：

D O I：

10.1007/PL00009387

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P, whose union covers P. Our algorithm runs in time O(n(4/3) log(5) n).

引用

收藏

页码：287 / 305

页数：19

相关论文

共 15 条

[1] ON STABBING LINES FOR CONVEX POLYHEDRA IN 3D [J].

AGARWAL, PK .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1994, 4 (04) :177-189

[2] PLANAR GEOMETRIC LOCATION-PROBLEMS [J].

AGARWAL, PK ;

SHARIR, M .

ALGORITHMICA, 1994, 11 (02) :185-195

[3] SELECTING DISTANCES IN THE PLANE [J].

AGARWAL, PK ;

ARONOV, B ;

SHARIR, M ;

SURI, S .

ALGORITHMICA, 1993, 9 (05) :495-514

[4]

[Anonymous], SIAM J COMPUT

[5] COMBINATORIAL COMPLEXITY-BOUNDS FOR ARRANGEMENTS OF CURVES AND SPHERES [J].

CLARKSON, KL ;

EDELSBRUNNER, H ;

GUIBAS, LJ ;

SHARIR, M ;

WELZL, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) :99-160

[6] APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2. [J].

CLARKSON, KL ;

SHOR, PW .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421

[7]

Eppstein D, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P131

[8] FINDING TAILORED PARTITIONS [J].

HERSHBERGER, J ;

SURI, S .

JOURNAL OF ALGORITHMS, 1991, 12 (03) :431-463

[9]

Jaromczyk J. W., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P303, DOI 10.1145/177424.178038

[10] An expander-based approach to geometric optimization [J].

Katz, MJ ;

Sharir, M .

SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1384-1408