Concepedia

Randomized Geometric Algorithms

Randomized Geometric Algorithms is a class of algorithms in computational geometry that solve problems on geometric objects by incorporating random choices into their design or execution to obtain provable performance guarantees—typically on expected running time or simplicity of analysis—that are superior or more robust than those of comparable deterministic geometric algorithms.

1K

Publications

56.4K

Citations

1.6K

Authors

650

Institutions

Publications per year

2017–2026

82

Parents

Children

Publications

1K

The quickhull algorithm for convex hulls

C. Bradford Barber, David Dobkin, Hannu Huhdanpaa · ACM Transactions on Mathematical Software · 1996 · 5.3K citations · Full text

, , +16

Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

Sanjeev Arora · Journal of the ACM · 1998 · 1.1K citations · Full text

, , +17

Optimal Search in Planar Subdivisions

David Kirkpatrick · SIAM Journal on Computing · 1983 · 751 citations

, , +13

A random polynomial-time algorithm for approximating the volume of convex bodies

Martin Dyer, Alan Frieze, Ravi Kannan · Journal of the ACM · 1991 · 701 citations · Full text

, , +12

On Constructing Minimum Spanning Trees in <i>k</i>-Dimensional Spaces and Related Problems

Andrew Chi-Chih Yao · SIAM Journal on Computing · 1982 · 608 citations

, , +16

1–5 of 1K

Authors

1.6K

  1. MS
    Micha Sharir

    Tel Aviv University, Israel

    34 publications · 1.7K citations

    21

    h-index

  2. PK
    Pankaj K. Agarwal

    Duke University, United States

    22 publications · 1.3K citations

    19

    h-index

  3. TM
    Timothy M. Chan

    University of Waterloo, Canada

    17 publications · 961 citations

    13

    h-index

  4. JS
    Joseph S. B. Mitchell

    Stony Brook University, United States

    12 publications · 372 citations

    12

    h-index

  5. BC
    Bernard Chazelle

    Princeton University, United States

    11 publications · 621 citations

    11

    h-index

1–5 of 1.6K

Institutions

650

  1. Tel Aviv University

    Tel Aviv, Israel

    28 h-index

    88 publications

    3.4K citations

  2. Carnegie Mellon University

    Pittsburgh, United States

    22 h-index

    38 publications

    3.7K citations

  3. Princeton University

    Princeton, United States

    21 h-index

    40 publications

    8.8K citations

  4. Duke University

    Durham, United States

    20 h-index

    36 publications

    1.8K citations

  5. University of Waterloo

    Waterloo, Canada

    20 h-index

    33 publications

    1.4K citations

  6. Max Planck Institute for Informatics

    Saarbrücken, Germany

    19 h-index

    39 publications

    1.9K citations

  7. New York University

    New York, United States

    19 h-index

    41 publications

    1.9K citations

  8. Courant Institute of Mathematical Sciences

    New York, United States

    19 h-index

    34 publications

    1.5K citations

1–8 of 650

Venues

  1. SIAM Journal on Computing

    52 publications · 4.1K citations

    32

    h-index

  2. Discrete & Computational Geometry

    50 publications · 2.4K citations

    27

    h-index

  3. Information Processing Letters

    46 publications · 2.6K citations

    24

    h-index

  4. Journal of Algorithms

    25 publications · 2.2K citations

    23

    h-index

  5. Algorithmica

    37 publications · 1.7K citations

    23

    h-index

1–5