Incremental and decremental maintenance of planar width

被引：7

作者：

Eppstein, D ^{[1
]}

机构：

[1] Univ Calif Irvine, Dept Informat & Comp Sci, Irvine, CA 92697 USA

来源：

JOURNAL OF ALGORITHMS | 2000年 / 37卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.2000.1107

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn(epsilon)) par update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and epsilon > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n(epsilon)). (C) 2000 Academic Press.

引用

页码：570 / 577

页数：8

共 16 条

[1]

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

[2] Efficient randomized algorithms for some geometric optimization problems [J].

Agarwal, PK ;

Sharir, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1996, 16 (04) :317-337

[3] DYNAMIC HALF-SPACE RANGE REPORTING AND ITS APPLICATIONS [J].

AGARWAL, PK ;

MATOUSEK, J .

ALGORITHMICA, 1995, 13 (04) :325-345

[4]

AGARWAL PK, 1997, LECT NOTES COMPUTER, V1272, P21

[5]

CHAN T, 1999, P 40 ANN IEEE S FDN, P92

[6] DIAMETER, WIDTH, CLOSEST LINE PAIR, AND PARAMETRIC SEARCHING [J].

CHAZELLE, B ;

EDELSBRUNNER, H ;

GUIBAS, L ;

SHARIR, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 10 (02) :183-196

[7] DYNAMIC EUCLIDEAN MINIMUM SPANNING-TREES AND EXTREMA OF BINARY FUNCTIONS [J].

EPPSTEIN, D .

DISCRETE & COMPUTATIONAL GEOMETRY, 1995, 13 (01) :111-122

[8] Average case analysis of dynamic geometric optimization [J].

Eppstein, D .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1996, 6 (01) :45-68

[9] COMPUTING THE WIDTH OF A SET [J].

HOULE, ME ;

TOUSSAINT, GT .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1988, 10 (05) :761-765

[10] ON MAINTAINING THE WIDTH AND DIAMETER OF A PLANAR POINT-SET ONLINE [J].

Janardan, Ravi .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1993, 3 (03) :331-344

← 1 2 →