On the stabbing number of a random Delaunay triangulation

DOI10.1016/J.COMGEO.2006.05.005zbMATH Open1105.65020OpenAlexW1976756638MaRDI QIDQ857055FDOQ857055

Prosenjit Bose, Luc 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

computational geometryDelaunay triangulationgraph diameterVoronoi diagramprobabilistic analysisproximity graphsstabbing number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Stabbing Delaunay tetrahedralizations
• Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation
• Walking in a Planar Poisson–Delaunay Triangulation: Shortcuts in the Voronoi Path
• New Stick Number Bounds from Random Sampling of Confined Polygons
• Efficiently navigating a random Delaunay triangulation
• Practical distribution-sensitive point location in triangulations
• 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

   Recommendations

• Title not available (Why is that?) 👍 👎
• On properties of random dissections and triangulations 👍 👎
• The stability of Delaunay triangulations 👍 👎
• On the number of higher order Delaunay triangulations 👍 👎
• On the Number of Higher Order Delaunay Triangulations 👍 👎
• A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case 👍 👎
• A note on point location in Delaunay triangulations of random points 👍 👎
• Random Delaunay simplexes in \({\mathbb{R}}^ m\) 👍 👎
• On degrees in random triangulations of point sets 👍 👎
• On degrees in random triangulations of point sets 👍 👎

This page was built for publication: On the stabbing number of a random Delaunay triangulation

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