Cylindrical Algebraic Decomposition and connected components

asked 2022-11-13 23:26:21 +0100

kevinfat gravatar image

From what I've read Sage has support for accessing QEPCAD which implements Cylindrical Algebraic Decomposition.

Given a collection of polynomial inequalities I would like to know if they define a single connected region or multiple regions. It looks to me that the Cylindrical Algebraic Decomposition can be used to determine that though I don't know how to get at that. Does QEPCAD support that question or do I need to understand a lot of details to implement that using QEPCAD?

edit retag flag offensive close merge delete

Comments

From reading documentation at https://doc.sagemath.org/html/en/refe... the answer appears to be Yes. Just count how many cells have required polynomial signs and check if this number is 1.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-11-14 06:12:57 +0100 )edit

I don't think cells represent largest connected regions.

kevinfat gravatar imagekevinfat ( 2022-11-15 04:12:41 +0100 )edit

Why? When we cross a boundary between two cells, the inequality corresponding to this boundary changes its sign. Hence, if there is a path connecting two points and preserving all inequalities along the way, it should not cross any cell boundaries, meaning that such a path must be entirely within a single cell.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-11-15 15:18:24 +0100 )edit