RANDOMIZATION YIELDS SIMPLE O(n log⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
From MaRDI portal
Publication:4016895
Recommendations
- scientific article; zbMATH DE number 1775407
- A Note on Randomized Polynomial Time
- The randomized complexity of initial value problems
- scientific article; zbMATH DE number 1566488
- The solution of some random NP-hard problems in polynomial expected time
- Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
- scientific article; zbMATH DE number 1559524
- Random pseudo-polynomial algorithms for some combinatorial programming problems
Cited in
(16)- A nearly parallel algorithm for the Voronoi diagram of a convex polygon
- An introduction to randomization in computational geometry
- Randomized incremental construction of Delaunay triangulations of nice point sets
- Can a randomized binary search have an \(O(1)\) complexity at least in practice?
- Three problems about simple polygons
- Computing a single cell in the overlay of two simple polygons
- BIARC APPROXIMATION, SIMPLIFICATION AND SMOOTHING OF POLYGONAL CURVES BY MEANS OF VORONOI-BASED TOLERANCE BANDS
- Dog Bites Postman
- A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
- Randomized incremental construction of Delaunay triangulations of nice point sets
- AN APPROXIMATE MORPHING BETWEEN POLYLINES
- Computing hereditary convex structures
- VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
- Fast skeleton construction
- Finding the medial axis of a simple polygon in linear time
- Efficient search for a minimum tree in a space with the l₁-norm
This page was built for publication: RANDOMIZATION YIELDS SIMPLE O(n log⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4016895)
