Concepedia

Randomized Incremental Construction

Randomized Incremental Construction is a computational geometry algorithmic technique that belongs to the class of incremental construction methods, distinguished by its incorporation of randomization in the insertion order of geometric primitives to achieve efficient expected-time complexity in arrangements of curves and randomized geometric algorithms.

23

Publications

1.4K

Citations

43

Authors

26

Institutions

Publications per year

2017–2026

1

Parents

Publications

23

Randomized incremental construction of Delaunay and Voronoi diagrams

Leonidas Guibas, Donald E. Knuth, Micha Sharir · Algorithmica · 1992 · 473 citations

, , +10

Randomized incremental construction of abstract Voronoi diagrams

Rolf Klein, Kurt Mehlhorn, Stefan Meiser · Computational Geometry · 1993 · 146 citations

, , +10

Incremental constructions con BRIO

Nina Amenta, Sunghee Choi, Günter Rote · 2003 · 111 citations

, , +12

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams

Pankaj K. Agarwal, Mark de Berg, Otfried Schwarzkopf · SIAM Journal on Computing · 1998 · 108 citations · Full text

, , +13

Faster construction of planar two-centers

David Eppstein · eScholarship (California Digital Library) · 1997 · 94 citations · Full text

, , +9

1–5 of 23

Authors

43

  1. MD
    Mark de Berg

    Utrecht University, Netherlands

    4 publications · 220 citations

    4

    h-index

  2. MS
    Micha Sharir

    Tel Aviv University, Israel

    4 publications · 558 citations

    4

    h-index

  3. OS
    Otfried Schwarzkopf

    Utrecht University, Netherlands

    4 publications · 220 citations

    4

    h-index

  4. HK
    Haim Kaplan

    Tel Aviv University, Israel

    2 publications · 34 citations

    2

    h-index

  5. GR
    Günter Rote

    Freie Universität Berlin, Germany

    2 publications · 128 citations

    2

    h-index

1–5 of 43

Institutions

26

  1. Utrecht University

    Utrecht, The Netherlands

    4 h-index

    8 publications

    440 citations

  2. Max Planck Institute for Informatics

    Saarbrücken, Germany

    3 h-index

    8 publications

    418 citations

  3. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    5 publications

    541 citations

  4. Courant Institute of Mathematical Sciences

    New York, United States

    2 h-index

    2 publications

    484 citations

  5. Duke University

    Durham, United States

    2 h-index

    2 publications

    128 citations

  6. Institut national de recherche en sciences et technologies du numérique

    Le Chesnay-Rocquencourt, France

    2 h-index

    2 publications

    92 citations

  7. University of California, Davis

    Davis, United States

    2 h-index

    2 publications

    128 citations

  8. The University of Texas at Austin

    Austin, United States

    2 h-index

    2 publications

    128 citations

1–8 of 26

Venues

  1. SIAM Journal on Computing

    3 publications · 191 citations

    3

    h-index

  2. Discrete & Computational Geometry

    2 publications · 86 citations

    2

    h-index

  3. Computational Geometry

    2 publications · 156 citations

    2

    h-index

  4. Theoretical Computer Science

    1 publications · 87 citations

    1

    h-index

  5. Journal of Cryptology

    1 publications · 15 citations

    1

    h-index

1–5