Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design

DOI10.1137/S0097539796305365MaRDI QIDQ4229412zbMATH OpenOpenAlexFDO

Authors Giuseppe Liotta, Roberto Tamassia, F. P. Preparata

Publication date 22 February 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539796305365

zbMATH Keywords

arithmetic precisiongeometric computingproximity queriesrobustness

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A low arithmetic-degree algorithm for computing proximity graphs
• Topology-oriented implementation -- an approach to robust geometric algorithms
• A paradigm for robust geometric algorithms
• LOCAL ROBUSTNESS AND ITS APPLICATION TO POLYHEDRAL INTERSECTION

Cited in

(17)

• Robustness of k-gon Voronoi diagram construction
• Checking the convexity of polytopes and the planarity of subdivisions
• Algebraic methods and arithmetic filtering for exact predicates on circle arcs
• Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications
• Reporting intersections among thick objects.
• Optimal and suboptimal robust algorithms for proximity graphs
• On constant factors in comparison-based geometric algorithms and data structures
• Computing the Implicit Voronoi Diagram in Triple Precision
• Robust Point-Location in Generalized Voronoi Diagrams
• A low arithmetic-degree algorithm for computing proximity graphs
• THE L_∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS
• A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
• Smoothing the Gap Between NP and ER
• Checking the convexity of polytopes and the planarity of subdivisions (extended abstract)
• VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
• An elementary algorithm for reporting intersections of red/blue curve segments
• The unpredictable deviousness of models

Describes a project that uses

Uses Software

• LEDA
• Hull

This page was built for publication: Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design

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