Finding lowest point in circles
I suspect you should be able to solve this with a sweepline algorithm, probably in $O(n \log n)$ time or something like that.
In particular, I suggest you build a data structure so that for any $x$, you can find the range of $y$-values that are in the intersection of all the circles.  You should be able to build such a data structure by mimicking the Bentley-Ottmann algorithm.  Decompose each circle into four quarter-circles (arcs that cover one-fourth of the perimeter of the circle).  Each quarter-circle takes the place of a line segment.  Each intersection between two quarter-circles is an &quot;event&quot;.  Then it is easy to answer your original question; each interval of $x$ values between two consecutive events corresponds to a single leaf in the tree, and you can quickly compute the lowest $y$ value in the intersection for that range of $x$ values, then do that for each such interval.  I haven't tried to work through all the details, so I suggest you check the specifics to see if this works out or if there is some challenge I've overlooked.