The paper by Lo, Matoušek, and Steiger entitled "Algorithms for Ham-Sandwich Cuts" gives an $O(n)$ algorithmin arbitrary dimensions (!), , where $n$ is the number of points. That's the best you can do, since you need to consider all such points.
The paper by Lo, Matoušek, and Steiger entitled "Algorithms for Ham-Sandwich Cuts" gives an $O(n)$ algorithm in arbitrary dimensions (!), where $n$ is the number of points. That's the best you can do, since you need to consider all such points.