4 RESULTS ON RANDOMIZED INCREMENTAL CONSTRUCTIONS

被引：90
作者：
CLARKSON, KL
MEHLHORN, K
SEIDEL, R
机构：
[1] AT&T BELL LABS,MURRAY HILL,NJ 07974
[2] MAX PLANCK INST INFORMAT,W-6600 SAARBRUCKEN,GERMANY
[3] UNIV SAARLAND,W-6600 SAARBRUCKEN,GERMANY
[4] UNIV CALIF BERKELEY,DIV COMP SCI,BERKELEY,CA 94720
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1993年 / 3卷 / 04期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0925-7721(93)90009-U
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We prove four results on randomized incremental constructions (RICs): an analysis of the expected behavior under insertion and deletions, a fully dynamic data structure for convex hull maintenance in arbitrary dimensions a tail estimate for the space complexity of RICs, a lower bound on the complexity of a game related to RICs.
引用
收藏
页码：185 / 212
页数：28
相关论文
共 21 条
  • [1] [Anonymous], 1987, EATCS MONOGRAPHS THE
  • [2] BOAS PV, 1977, MATH SYST THEORY, V10, P99
  • [3] APPLICATIONS OF RANDOM SAMPLING TO ONLINE ALGORITHMS IN COMPUTATIONAL GEOMETRY
    BOISSONNAT, JD
    DEVILLERS, O
    SCHOTT, R
    TEILLAUD, M
    YVINEC, M
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 8 (01) : 51 - 71
  • [4] Chazelle B., 1991, 2ND ANN ACM SIAM S D, P441
  • [5] CLARKSON KL, 1989, J DISCRETE COMPUT GE, P387
  • [6] Devillers O., 1992, Computational Geometry: Theory and Applications, V2, P55, DOI 10.1016/0925-7721(92)90025-N
  • [7] DEVILLERS O, 1992, J COMPUT GEOM APPL, V2, P621
  • [8] DIETZFELBINGER M, 1988, IEEE S F COMPUTER SC, P524
  • [9] GUIBAS LJ, 1992, ALGORITHMICA, V7, P831
  • [10] BOUNDED ORDERED DICTIONARIES IN O(LOG LOG N) TIME AND O(N) SPACE
    MEHLHORN, K
    NAHER, S
    [J]. INFORMATION PROCESSING LETTERS, 1990, 35 (04) : 183 - 189
123