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 条

[11] Incremental and decremental maintenance of planar width [J].

Eppstein, D .

JOURNAL OF ALGORITHMS, 2000, 37 (02) :570-577

[12]

Eppstein D., 1992, ORSA Journal on Computing, V4, P360, DOI 10.1287/ijoc.4.4.360

[13] APPLICATIONS OF A SEMIDYNAMIC CONVEX-HULL ALGORITHM [J].

HERSHBERGER, J ;

SURI, S .

BIT, 1992, 32 (02) :249-267

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

HOULE, ME ;

TOUSSAINT, GT .

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

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

[16] LINEAR OPTIMIZATION QUERIES [J].

MATOUSEK, J .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1993, 14 (03) :432-448

[17]

MEHLHORN K, 1984, DATA STRUCTURES ALGO, V3

[18] MAINTENANCE OF CONFIGURATIONS IN THE PLANE [J].

OVERMARS, MH ;

VANLEEUWEN, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1981, 23 (02) :166-204

[19]

Preparata F., 2012, Computational geometry: an introduction

[20]

ROTE G, 1993, P 5 CAN C COMP GEOM, P258

← 1 2 3 →