Ham-sandwich cuts in R d
Jiřı́ Matoušek, Chi-Yuan Lo, William Steiger · 1992
Lo and Steiger resolved the complexity question for computing a planar ham-sandwich cut by giving an optimal linear-time algorithm. We show how to generalize the ideas to every fixed dimension d > 2 by describing an algorithm that computes a ham-sandwich cut in Rd in time O(nd–1–a(d)), for some a(d) > 0 (going to zero as d increases). For d = 3,4, the running time is almost proportional to ed–1(n;n/2), where dd(k;n) denotes the maximal number of k-sets over sets of n points in Rd, and with the current best bounds, we get O(n3/2 log2n/log n) running time for d = 3 and O(n8/3+e) for d=4. We also give a linear time algorithm for three dimensional ham-sandwich cuts when the three sets are suitably separated.