Optimal and suboptimal robust algorithms for proximity graphs

DOI10.1016/S0925-7721(02)00129-3MaRDI QIDQ1873154zbMATH OpenOpenAlexWikidataFDO

Authors Giuseppe Liotta, Ferran Hurtado, Henk Meijer

Publication date 19 May 2003

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0925-7721(02)00129-3

zbMATH Keywords

algorithmbeta skeletonscomputational geometryGabriel graphsgraph drawingproximity graphsrobustness

Mathematics Subject Classification ID

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

Review text

The authors show a numerically robust algorithm that computes Gabriel graphs in quadratic time and degree 2. Also it is shown how a \(\rho\)-spectrum can be computed in optimal \(O(n^2)\) time.

Recommendations

• scientific article; zbMATH DE number 1830717
• A low arithmetic-degree algorithm for computing proximity graphs
• scientific article; zbMATH DE number 4115994
• Time-optimal proximity graph computations on enhanced meshes
• Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design

Cites work

• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• Efficient algorithms for line and curve segment intersection using restricted predicates
• On the shape of a set of points in the plane
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Reporting curve segment intersections using restricted predicates
• Robust Plane Sweep for Intersecting Segments
• Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design
• The \(\gamma\)-neighborhood graph
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Topologically sweeping an arrangement

Cited in

(9)

• Output-sensitive algorithm for computing -skeletons
• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• -skeletons for a set of line segments in R^2
• scientific article; zbMATH DE number 2086250 (Why is no real title available?)
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• Algorithms for computing the optimal transitive approximation of a proximity relation
• A low arithmetic-degree algorithm for computing proximity graphs
• scientific article; zbMATH DE number 1830717 (Why is no real title available?)
• Essential constraints of edge-constrained proximity graphs

This page was built for publication: Optimal and suboptimal robust algorithms for proximity graphs

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