A low arithmetic-degree algorithm for computing proximity graphs

DOI10.1142/S021819591850005XMaRDI QIDQ4557732zbMATH OpenOpenAlexWikidataFDO

Authors Fabrizio d'Amore, Paolo G. Franciosa

Publication date 26 November 2018

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s021819591850005x

zbMATH Keywords

geometric graphsEuclidean minimum spanning treerobust computationarithmetic degree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Optimal and suboptimal robust algorithms for proximity graphs
• scientific article; zbMATH DE number 1830717
• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Computing relative neighbourhood graphs in the plane

Cites work

• scientific article; zbMATH DE number 437554 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 1436136 (Why is no real title available?)
• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• An O(n log n) algorithm for the all-nearest-neighbors problem
• An adaptable and extensible geometry kernel
• An all-round sweep algorithm for 2-dimensional nearest-neighbor problems
• Computing planar Voronoi diagrams in double precision, a further example of degree-driven algorithm design
• Efficient exact evaluation of signs of determinants
• Efficient perturbations for handling geometric degeneracies
• Euclidean minimum spanning trees and bichromatic closest pairs
• Exact geometric and algebraic computations in CGAL
• Finding Minimum Spanning Trees
• Minimum Spanning Trees in k-Dimensional Space
• NUMERICAL STABILITY OF ALGORITHMS FOR 2D DELAUNAY TRIANGULATIONS
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On the angle restricted nearest neighbor problem
• On the degree of standard geometric predicates for line transversals in 3D
• Robust Plane Sweep for Intersecting Segments
• Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design
• Robustness of k-gon Voronoi diagram construction
• Strong Connectivity in Directional Nearest-Neighbor Graphs
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The computational geometry algorithms library CGAL
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• The unpredictable deviousness of models
• Towards exact geometric computation

Cited in

(4)

• scientific article; zbMATH DE number 1830717 (Why is no real title available?)
• Algorithms for computing the optimal transitive approximation of a proximity relation
• Optimal and suboptimal robust algorithms for proximity graphs
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric

Describes a project that uses

Uses Software

• CGAL

This page was built for publication: A low arithmetic-degree algorithm for computing proximity graphs

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