RANDOMIZATION YIELDS SIMPLE O(n log⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS

DOI10.1142/S021819599200007XzbMath0761.68094OpenAlexW2162050448MaRDI QIDQ4016895

Olivier Devillers

Publication date: 16 January 1993

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s021819599200007x

zbMATH Keywords

polygonrandomized algorithmsDelaunay triangulationskeletoninfluence grapheuclidean minimum spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (13)

Computing a single cell in the overlay of two simple polygons ⋮ A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon ⋮ An introduction to randomization in computational geometry ⋮ AN APPROXIMATE MORPHING BETWEEN POLYLINES ⋮ Fast skeleton construction ⋮ Three problems about simple polygons ⋮ BIARC APPROXIMATION, SIMPLIFICATION AND SMOOTHING OF POLYGONAL CURVES BY MEANS OF VORONOI-BASED TOLERANCE BANDS ⋮ Computing hereditary convex structures ⋮ Unnamed Item ⋮ VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments ⋮ Randomized incremental construction of Delaunay triangulations of nice point sets ⋮ A nearly parallel algorithm for the Voronoi diagram of a convex polygon ⋮ Dog Bites Postman

This page was built for publication: RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS