A fully dynamic algorithm for planar width

被引：8

作者：

Chan, TA ^{[1
]}

机构：

[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2003年 / 30卷 / 01期

关键词：

D O I：

10.1007/s00454-003-2923-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show how to maintain the width of a set of n planar. points subject to insertions and deletions of points in O(rootnlog(3) n) amortized time per update. Previously, no fully dynamic algorithm with a guaranteed sublinear time bound was known.

引用

页码：17 / 24

页数：8

共 21 条

[1]

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

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

AGARWAL, PK ;

MATOUSEK, J .

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

[3] 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

[4]

[Anonymous], J ALGORITHMS

[5]

Brodal GS, 2002, ANN IEEE SYMP FOUND, P617, DOI 10.1109/SFCS.2002.1181985

[6]

Chan TM, 2002, SIAM PROC S, P474

[7] Dynamic planar convex hull operations in near-logarithmic amortized time [J].

Chan, TM .

JOURNAL OF THE ACM, 2001, 48 (01) :1-12

[8] ON THE CONVEX LAYERS OF A PLANAR SET [J].

CHAZELLE, B .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :509-517

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

EPPSTEIN, D .

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

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

Eppstein, D .

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

← 1 2 3 →