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.
Charles Chen
- 502
- 5
- 14