Disk with root in center with no other roots in polynomial Say we have a polynomial $p$ with roots $r_1,r_2...r_n$, I'm looking for a way to find a disk which, if placed on the center of any root, does not contain any other root (multiple roots considered as one). It does not have to be the largest disk, but the larger disk, the better.
Edit: I do not know the roots in advance, only the coefficients. Calculating them is not an option.
I have absolutely no idea on how to go about this.
 A: The problem you describe is called root isolation.
See for instance these papers:


*

*A Simple But Exact and Efficient Algorithm for Complex Root Isolation and its Complexity Analysis

*An Efficient and Exact Subdivision Algorithm for Isolating Complex Roots of a Polynomial and its Complexity Analysis

*Empirical Study of an Evaluation-Based Subdivision Algorithm for Complex Root Isolation
and others at http://cs.nyu.edu/exact/papers/.
A: First step, get rid of multiple roots by determining the gcd of $p$ and its derivative $p'$ and if it is non-constant, dividing $p/gcd(p,p')$. There are methods to determine an approximate gcd for non-exact coefficients.
Now assuming that $p$ is square-free, compute the discriminant of $p$, i.e., a normalized multiple of the resultant of $p$ and $p'$. In the normalized version, disregarding the signs, one has
$$
|disc(p)|=\prod_{i<j}|z_i-z_j|^2
$$ 
if $n=\deg p$ and $z_1,...,z_n$ are the roots of $p$. For the following, assume that $|z_1-z_2|$ is the minimal distance. All other distances will be smaller than $2R$ if $R$ is a bound on the magnitudes of the roots (Cauchy, Lagrange, perhaps refined via Graeffe iterations). Then
$$
|z_1-z_2|\ge r=\frac{\sqrt{disc(p)}}{(2R)^{(n+1)(n-2)/2}}
$$

In non-exact arithmetic, if the accuracy used for the approximate gcd is high then close-by roots may not be treated as the same root, so the resulting discriminant and the resulting root separating radius $r$ will reflect this small distance. Going the other way, allowing a wide margin in computing the approximate gcd will then result in a root separating radius that would be called more correctly a root-cluster separating radius.
