Expected time analysis for Delaunay point location

DOI10.1016/j.comgeo.2004.02.002zbMath1064.65018OpenAlexW2078707782WikidataQ29306847 ScholiaQ29306847MaRDI QIDQ1882851

C. Lemaire, J.-M. Moreau, Luc P. Devroye

Publication date: 1 October 2004

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

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

zbMATH Keywords

probabilistic analysisVoronoi diagramcomputational geometryDelaunay triangulationrandom treepoint location

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Related Items (9)

Practical distribution-sensitive point location in triangulations ⋮ Optimal Delaunay and Voronoi Quantization Schemes for Pricing American Style Options ⋮ On the stabbing number of a random Delaunay triangulation ⋮ Walking in a Planar Poisson–Delaunay Triangulation: Shortcuts in the Voronoi Path ⋮ A local search algorithm for ray-convex polyhedron intersection ⋮ Parallel Delaunay triangulation in three dimensions ⋮ Efficiently navigating a random Delaunay triangulation ⋮ Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation ⋮ Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some inequalities relating to the partial sum of binomial probabilities
• Refinements to nearest-neighbor searching in k-dimensional trees
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• An all-round sweep algorithm for 2-dimensional nearest-neighbor problems
• On the randomized construction of the Delaunay tree
• A note on point location in Delaunay triangulations of random points
• Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations
• Intersections with random geometric objects
• Some extensions of an inequality of Vapnik and Chervonenkis
• Squarish k-d Trees
• THE DELAUNAY HIERARCHY
• THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Optimal Expected-Time Algorithms for Closest Point Problems
• Multidimensional binary search trees used for associative searching
• Computing Dirichlet Tessellations in the Plane
• Walking in a triangulation
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Binary Search Trees of Bounded Balance
• Analysis of range search for random \(k-d\) trees

This page was built for publication: Expected time analysis for Delaunay point location