# Connectedness of semialgebraic sets via CAD

I do not know whether there is a standard or some traditional ways to decide whether a semialgebraic set is connected or not.

One way I know is the cylindrical algebraic decomposition (CAD) algorithm. I have read some papers on the CAD algorithm, and they mentioned connectedness can be done by using CAD. However, I have not seen any explanation or example.

Can CAD do the connectedness of semialgebraic sets and how? Or any other theoretical way to decide the connectedness of semialgebraic sets?

• Over what field? Jun 2, 2016 at 16:20
• Only real numbers. Jun 2, 2016 at 16:53

We can use the CAD algorithm to decompose a semialgebraic set $$S$$ into a finite set of connected semialgebraic components $$S_i$$.
We can test whether two such components are adjacent, meaning $$\bar{S_i}\cap\bar{S_j}\cap S\neq\emptyset$$, using the standard decision procedure for real-closed fields.
Then we can form a graph $$G$$ using the components $$S_i$$ as vertices, with an edge between $$S_i$$ and $$S_j$$ iff they are adjacent in the above sense.
Finally we can test whether $$G$$ is connected, and this will be equivalent to whether $$S$$ is connected.