A tail estimate for Mulmuley's segment intersection algorithm
From MaRDI portal
Publication:5204337
DOI10.1007/3-540-55719-9_94zbMath1425.68436OpenAlexW1547523622MaRDI QIDQ5204337
Raimund Seidel, Ji{ří} Matoušek
Publication date: 4 December 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55719-9_94
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)
Related Items (1)
Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
Cites Work
- The complexity and construction of many faces in arrangements of lines and of segments
- A guided tour of Chernoff bounds
- The power of geometric duality
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- The number of edges of many faces in a line segment arrangement
- Reporting and counting segment intersections
- Applications of random sampling in computational geometry. II
- A method for obtaining randomized algorithms with small tail probabilities
- Algorithms for Reporting and Counting Geometric Intersections
- Constructing Arrangements of Lines and Hyperplanes with Applications
- An optimal algorithm for intersecting line segments in the plane
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A tail estimate for Mulmuley's segment intersection algorithm
