A unified approach to tail estimates for randomized incremental construction

DOI10.4230/LIPIcs.STACS.2019.58OpenAlexW3204367131MaRDI QIDQ5088886

Sandeep Sen

Publication date: 18 July 2022

Full work available at URL: https://research.snu.edu.in/publication/a-unified-approach-to-tail-estimates-for-randomized-incremental

zbMATH Keywords

martingalelower boundtail estimatesRic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Small-dimensional linear programming and convex hulls made easy
• Randomized incremental construction of Delaunay and Voronoi diagrams
• On tail probabilities for martingales
• Applications of random sampling in computational geometry. II
• A simple randomized sieve algorithm for the closest-pair problem
• Large Deviations for Quicksort
• Four results on randomized incremental constructions
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: A unified approach to tail estimates for randomized incremental construction