Megiddo's Parametric Search Technique
                                                                                
Suppose you have an arrangement of n lines, and you want to find a
vertex in this arrangement, such that half of the vertices lie to the
left of it, and half lie to the right. Since there are O(n^2)
vertices in an arrangement, an obvious algorithm would take O(n^2)
time. Megiddo's technique allows for an efficient algorithm that
would take O(n log^2 n) time. We will discuss his technique as well
as its application to a number of problems in computational geometry
and graph theory.