How to find the largest disk in a square when there are points we must avoid? We have $n$ points $X =\{x_1, x_2, \dots, x_n\}$ inside (let's say) the unit square $Q$. We must find a disk $D\subset Q$ such that none of the points of $X$ are inside the disk. (The points can be on the boundary of $D$, otherwise we couldn't even find a solution, I guess.)
What I've done so far (I'm trying to make a program to solve this) is to construct the Delaunay triangulation of the points of $X$ and check the circumscribing circle of every triangle. I only take into account the circles that stay inside $Q$.
Here is an example of the problem and the disk found by my program:

Then, I think, I should check the circles that are solutions to the Apollonian problem of being tangent to the sides of $Q$ and to a pair of points on the "outerlayer" of the triangulation (the ones forming the convex hull of the points), or tangent to two sides and one point. For these circles I have to check if there are any points of $X$ inside the solution circle (since this could of course happen if I check every pair of points).
Will this type of handling solve the problem?

Sounds mostly feasible. You'll test $O(n)$ circles this way. However, I'm afraid you need to be more careful with the convex hull vs. square edges part.
See for example the large circle in the lower left of your image. It extends beond the left image (=square) boundary, and if you would construct the circle that touches the left boundary and passes through the same points of the convex hull, it would contain the third vertex of that triangle. I suppose you must also check all pairs consisting of one convex hull vertex and one "next inner" vertex (third vertex of a triangle with one edge belonging to the convex hull).
