CAD Adjacency Computation Using Validated Numerics

DOI10.1145/3087604.3087641MaRDI QIDQ5119969zbMATH OpenOpenAlexWikidataFDO

Authors Adam Strzeboński

Publication date 9 September 2020

Published in Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.06856

zbMATH Keywords

cell adjacencyconnected componentscylindrical algebraic decompositiontopology of semialgebraic sets

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Symbolic computation and algebraic computation (68W30)

Abstract: We present an algorithm for computation of cell adjacencies for well-based cylindrical algebraic decomposition. Cell adjacency information can be used to compute topological operations e.g. closure, boundary, connected components, and topological properties e.g. homology groups. Other applications include visualization and path planning. Our algorithm determines cell adjacency information using validated numerical methods similar to those used in CAD construction, thus computing CAD with adjacency information in time comparable to that of computing CAD without adjacency information. We report on implementation of the algorithm and present empirical data.

Recommendations

• Adherence is better than adjacency: computing the Riemann index using CAD
• scientific article; zbMATH DE number 195165
• scientific article; zbMATH DE number 51816
• Computer aided geometry
• Computer-aided construction of finite geometric spaces: Automated verification of geometric constraints
• A Numerical Framework to Simplify CAD Models for Reliable Estimates of Physical Quantities
• Reconstructing the topology of a CAD model -- a discrete approach
• Reconstructing the topology of a CAD model -- a discrete approach

Cited in

(6)

• Application of quantifier elimination to inverse buckling problems
• Validity proof of Lazard's method for CAD construction
• scientific article; zbMATH DE number 4180837 (Why is no real title available?)
• Computing with Tarski formulas and semi-algebraic sets in a web browser
• CAD and topology of semi-algebraic sets
• Merging adjacent cells during single cell construction

This page was built for publication: CAD Adjacency Computation Using Validated Numerics

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