FINDING K-POINTS WITH MINIMUM DIAMETER AND RELATED PROBLEMS

被引：63

作者：

AGGARWAL, A

IMAI, H

KATOH, N

SURI, S

机构：

[1] IBM CORP,THOMAS J WATSON RES CTR,YORKTOWN HTS,NY 10598

[2] KYUSHU UNIV,FUKUOKA 812,JAPAN

[3] KOBE UNIV COMMERCE,KOBE,JAPAN

[4] BELL COMMUN RES INC,MORRISTOWN,NJ 07960

来源：

JOURNAL OF ALGORITHMS | 1991年 / 12卷 / 01期

关键词：

D O I：

10.1016/0196-6774(91)90022-Q

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let S be a set consisting of n points in the plane. We consider the problem of finding k points of S that form a "small" set under some given measure, and present efficient algorithms for several natural measures including the diameter and the variance. © 1991.

引用

页码：38 / 56

页数：19

共 15 条

[1] A LINEAR-TIME ALGORITHM FOR COMPUTING THE VORONOI DIAGRAM OF A CONVEX POLYGON [J].

AGGARWAL, A ;

GUIBAS, LJ ;

SAXE, J ;

SHOR, PW .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) :591-604

[2]

AGGARWAL A, 1989, 3RD P ANN ACM S COMP, P278

[3]

Andrews HC, 1972, INTRO MATH TECHNIQUE

[4]

ASANO T, 1990, 6TH P INT C THEOR AP

[5]

ASANO T, 1988, 4TH P ANN ACM S COMP, P252

[6] VORONOI DIAGRAMS AND ARRANGEMENTS [J].

EDELSBRUNNER, H ;

SEIDEL, R .

DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (01) :25-44

[7]

EPPSTEIN D, IN PRESS DISCRETE CO

[8]

Hartigan JohnA., 1975, CLUSTERING ALGORITHM

[9]

HERSHBERGER J, 1989, 5TH P ANN ACM S COMP

[10]

HERSHBERGER J, IN PRESS J ALGORITHM

← 1 2 →