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


From reading documentation at 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