Optimal and suboptimal robust algorithms for proximity graphs

DOI10.1016/S0925-7721(02)00129-3zbMath1021.65009OpenAlexW2066852991WikidataQ62042614 ScholiaQ62042614MaRDI QIDQ1873154

Giuseppe Liotta, Ferran Hurtado, Henk G. 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

algorithmrobustnesscomputational geometrygraph drawingGabriel graphsproximity graphsbeta skeletons

Mathematics Subject Classification ID

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

Related Items

$$\beta $$-skeletons for a Set of Line Segments in $$R^2 $$

Cites Work

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