Sigma-local graphs

DOI10.1016/J.JDA.2008.10.002MaRDI QIDQ2266933zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid

Publication date 26 February 2010

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2008.10.002

zbMATH Keywords

geometric graphsproximity graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Local properties of geometric graphs
• Improved local algorithms for spanner construction
• Abstract sphere-of-influence graphs
• Local geometric spanners
• Local polyhedra and geometric graphs

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A time-optimal parallel algorithm for three-dimensional convex hulls
• Algorithms for Reporting and Counting Geometric Intersections
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Classes of graphs which approximate the complete Euclidean graph
• Empty region graphs
• Fast detection of polyhedral intersection
• Local polyhedra and geometric graphs
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On nearest-neighbor graphs
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Relative neighborhood graphs in three dimensions
• The \(\gamma\)-neighborhood graph
• The relative neighborhood graph for mixed feature variables

Cited in

(3)

• \((1+\varepsilon)\)-ANN data structure for curves via subspaces of bounded doubling dimension
• Local polyhedra and geometric graphs
• Local properties of geometric graphs

This page was built for publication: Sigma-local graphs

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