PLANAR GEOMETRIC LOCATION-PROBLEMS

被引：42

作者：

AGARWAL, PK

SHARIR, M

机构：

[1] TEL AVIV UNIV,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL

[2] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

来源：

ALGORITHMICA | 1994年 / 11卷 / 02期

关键词：

FACILITY LOCATION; PARAMETRIC SEARCHING; DUALITY; PLANAR ARRANGEMENTS;

D O I：

10.1007/BF01182774

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an O(n(2) log(3) n) algorithm for the two-center problem, in which we are given a set S of n points in the plane and wish to find two closed disks whose union contains S so that the larger of the two radii is as small as possible. We also give an O(n(2) log(5) n) algorithm for solving the two-line-center problem, where we want to find two strips that cover S whose maximum width is as small as possible. The best previous solutions of both problems require O(n(3)) time.

引用

页码：185 / 195

页数：11

共 13 条

[1]

Agarwal P. K., 1991, Computational Geometry: Theory and Applications, V1, P65, DOI 10.1016/0925-7721(91)90001-U

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