2017/04/22 by Adam Strzeboński, Strzebonski, Adam
Computer Science · Engineering · #68W30 #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #G.4 #I.1.2 #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1704.06856
openalex publication_date 2017/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.