Practical distribution-sensitive point location in triangulations

DOI10.1016/j.cagd.2013.02.004zbMath1283.65014MaRDI QIDQ2637075

Olivier Devillers, Pedro Machado Manhães de Castro

Publication date: 19 February 2014

Published in: Computer Aided Geometric Design (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cagd.2013.02.004

zbMATH Keywords

algorithm; geometric graph; Delaunay triangulation; point location; jump \& walk; keep, jump, \& climb; keep, jump, \& walk

Mathematics Subject Classification ID

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

Uses Software

• CGAL
• Stony Brook
• Spatial Sorting
• 2D triangulations
• point location strategies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proximate point searching
• On the asymptotic growth rate of some spanning trees embedded in \(\mathbb R^d\)
• A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces
• Stabbing Delaunay tetrahedralizations
• On the stabbing number of a random Delaunay triangulation
• Cost of sequential connection for points in space
• Convex hulls of samples from spherically symmetric distributions
• A note on point location in Delaunay triangulations of random points
• Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations
• General spacefilling curve heuristics and limit theory for the traveling salesman problem
• On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
• Expected time analysis for Delaunay point location
• Expected asymptotically optimal planar point location
• Lower bounds for expected-case planar point location
• Structural filtering: a paradigm for efficient and exact geometric programs
• Optimum binary search trees
• A simple entropy-based algorithm for planar point location
• THE DELAUNAY HIERARCHY
• WALKING IN A TRIANGULATION
• Spacefilling curves and the planar travelling salesman problem
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• Optimal Search in Planar Subdivisions
• Computing Dirichlet Tessellations in the Plane
• Complexity of the delaunay triangulation of points on surfaces the smooth case
• Proximate planar point location
• A static optimality transformation with applications to planar point location
• A pedagogic JavaScript program for point location strategies
• An experimental study of point location in planar arrangements in CGAL
• Algorithms – ESA 2004
• Sublinear Geometric Algorithms