On the stabbing number of a random Delaunay triangulation

DOI10.1016/J.COMGEO.2006.05.005MaRDI QIDQ857055zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1786679
• 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

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3633698 (Why is no real title available?)
• scientific article; zbMATH DE number 1195776 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1040020 (Why is no real title available?)
• scientific article; zbMATH DE number 1079755 (Why is no real title available?)
• scientific article; zbMATH DE number 1182923 (Why is no real title available?)
• scientific article; zbMATH DE number 1182924 (Why is no real title available?)
• scientific article; zbMATH DE number 1522924 (Why is no real title available?)
• scientific article; zbMATH DE number 1424308 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Computing Dirichlet Tessellations in the Plane
• Delaunay graphs are almost as good as complete graphs
• Expected time analysis for Delaunay point location
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Faster shortest-path algorithms for planar graphs
• Intersections with random geometric objects
• On the size of a random sphere of influence graph
• Optimal Expected-Time Algorithms for Closest Point Problems
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Probability Inequalities for Sums of Bounded Random Variables
• THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
• The analysis of a nested dissection algorithm
• Weighted sums of certain dependent random variables

Cited in

(8)

• Convex subdivisions with low stabbing numbers
• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity
• Stabbing Delaunay tetrahedralizations
• New Stick Number Bounds from Random Sampling of Confined Polygons
• Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation
• Practical distribution-sensitive point location in triangulations
• Walking in a Planar Poisson–Delaunay Triangulation: Shortcuts in the Voronoi Path
• A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee

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)