Ask Your Question

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

1 Answer

Sort by ยป oldest newest most voted

answered 2023-01-08 21:40:50 +0100

kevinfat gravatar image

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.

qf = qepcad_formula
qepcad(qf.connected_subset(a, a^2 - 1 > 0))
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


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

Seen: 156 times

Last updated: Jan 08 '23