I haven't seen that randomized algo to intersecting halfplanes earlier, but I think it's worth noting that main idea is almost the same as in Smallest Enclosing Circle problem (does there even exist deterministic algo with similar complexity?)

I think that I know a different solution to the half-plane problem. Instead of doing binary search, let the value gradually decrease and look at the polygon where O must be located. Initially, when , this polygon is the same as the input polygon. When the value is decreased, the sides move inwards at constant speed which can be determined in linear time using rotating calipers algorithm. The lengths of the sides decrease linearly, so it is possible to find the times when each length would reach zero. When the length of a side becomes zero, adjacent sides will begin shrinking faster, so it is necessary to emulate this process and to recompute the times for adjacent sides when one of the sides disappears. This can be easily done in time using a heap. So, this solution works in time, doesn't use binary search and is completely deterministic.