# Cylindrical Algebraic Decomposition and connected components

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 close merge delete

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.

( 2022-11-14 06:12:57 +0100 )edit

I don't think cells represent largest connected regions.

( 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.

( 2022-11-15 15:18:24 +0100 )edit

Sort by ยป oldest newest most voted

So I figured out how to compile sage from source with qepcad. There is already a connectivity test in qepcad. For example the following works.

var('a')
qepcad(qf.connected_subset(a, a^2 - 1 > 0))
more