5
$\begingroup$

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?

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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