On the stabbing number of a random Delaunay triangulation

DOI10.1016/j.comgeo.2006.05.005zbMath1105.65020OpenAlexW1976756638MaRDI QIDQ857055

Prosenjit Bose, Luc P. Devroye

Publication date: 14 December 2006

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2006.05.005

zbMATH Keywords

probabilistic analysisVoronoi diagramcomputational geometryDelaunay triangulationgraph diameterproximity graphsstabbing number

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Practical distribution-sensitive point location in triangulations, Walking in a Planar Poisson–Delaunay Triangulation: Shortcuts in the Voronoi Path, Efficiently navigating a random Delaunay triangulation, Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation, A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee, Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity, Convex subdivisions with low stabbing numbers

Cites Work

• Delaunay graphs are almost as good as complete graphs
• The analysis of a nested dissection algorithm
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Intersections with random geometric objects
• Expected time analysis for Delaunay point location
• Weighted sums of certain dependent random variables
• THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• A Separator Theorem for Planar Graphs
• Optimal Expected-Time Algorithms for Closest Point Problems
• Applications of a Planar Separator Theorem
• Computing Dirichlet Tessellations in the Plane
• On the size of a random sphere of influence graph
• Probability Inequalities for Sums of Bounded Random Variables
• Faster shortest-path algorithms for planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item