A tail estimate for Mulmuley's segment intersection algorithm

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

zbMATH Keywords

isoperimetric inequalitycomputational geometryvertical extensionmarked vertexblue edge

Mathematics Subject Classification ID

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