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?

  • 1
    $\begingroup$ Over what field? $\endgroup$ Jun 2, 2016 at 16:20
  • $\begingroup$ Only real numbers. $\endgroup$
    – user91646
    Jun 2, 2016 at 16:53

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy