Randomized geometric algorithms and pseudorandom generators

DOI10.1007/BF01940875zbMath0857.68056OpenAlexW2053165180MaRDI QIDQ1923860

Ketan D. Mulmuley

Publication date: 13 October 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940875

zbMATH Keywords

pseudorandom generatorsrandomized incremental algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items

Universal profinite domains, On Church's formal theory of functions and functionals. The \(\lambda\)- calculus: Connections to higher type recursion theory, proof theory, category theory, A derandomization using min-wise independent permutations, Unnamed Item, Unnamed Item, Markov incremental constructions, Fingerprints for highly similar streams, On (ε,k)‐min‐wise independent permutations, Min-wise independent permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A deterministic view of random sampling and its use in geometry
• On the construction of abstract Voronoi diagrams
• On levels in arrangements and Voronoi diagrams
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• \(\epsilon\)-nets and simplex range queries
• Small-dimensional linear programming and convex hulls made easy
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Applications of random sampling to on-line algorithms in computational geometry
• Applications of random sampling in computational geometry. II
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Randomized algorithms and pseudorandom numbers
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Linear Programming in Linear Time When the Dimension Is Fixed
• An optimal algorithm for intersecting line segments in the plane