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.
|
2 | deleted 28 characters in body | ||
|
|
||||
|
|
1 |
|
||
|
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. |
||||
