A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs

DOI10.1142/S021819591850005XzbMath1403.68316OpenAlexW2901754088WikidataQ128940224 ScholiaQ128940224MaRDI QIDQ4557732

Fabrizio d'Amore, Paolo Giulio 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)

Uses Software

• CGAL

Cites Work

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

This page was built for publication: A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs