  The yolk is an important concept in spatial voting games as it generalises
the equilibrium and provides bounds on the uncovered set. We present
near-linear time algorithms for computing the yolk in the spatial voting model
in the plane. To the best of our knowledge our algorithm is the first algorithm
that does not require precomputing the median lines and hence able to break the
existing $O(n^{4/3})$ bound which equals the known upper bound on the number of
median lines. We avoid this requirement by using Megiddo's parametric search,
which is a powerful framework that could lead to faster algorithms for many
other spatial voting problems.
