A tail estimate for Mulmuley's segment intersection algorithm

DOI10.1007/3-540-55719-9_94MaRDI QIDQ5204337zbMATH OpenOpenAlexFDO

Authors 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

blue edgecomputational geometryisoperimetric inequalitymarked vertexvertical extension

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Recommendations

• Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
• scientific article; zbMATH DE number 742952
• An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
• Reporting and counting segment intersections
• An optimal algorithm for intersecting line segments in the plane

Cites work

• A guided tour of Chernoff bounds
• A method for obtaining randomized algorithms with small tail probabilities
• Algorithms for Reporting and Counting Geometric Intersections
• An optimal algorithm for intersecting line segments in the plane
• Applications of random sampling in computational geometry. II
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Constructing Arrangements of Lines and Hyperplanes with Applications
• scientific article; zbMATH DE number 431985 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 4128851 (Why is no real title available?)
• scientific article; zbMATH DE number 742952 (Why is no real title available?)
• Reporting and counting segment intersections
• The complexity and construction of many faces in arrangements of lines and of segments
• The number of edges of many faces in a line segment arrangement
• The power of geometric duality

Cited in

(2)

• scientific article; zbMATH DE number 742952 (Why is no real title available?)
• Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection

This page was built for publication: A tail estimate for Mulmuley's segment intersection algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204337)