Algorithms for ham-sandwich cuts |
| |
Authors: | Chi-Yuan Lo J Matou?ek W Steiger |
| |
Institution: | (1) AT&T Bell Laboratories, 600 Mountain Avenue, 07974 Murray Hill, NJ, USA;(2) Charles University, Malostranské nám, 25, 118 00 Praha 1, Czech Republic;(3) Free University Berlin, Arnimallee 2-6, D-14195 Berlin, Germany;(4) Rutgers University, 08903 Piscataway, NJ, USA |
| |
Abstract: | Given disjoint setsP
1,P
2, ...,P
d
inR
d
withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP
i
. We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement
ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR
d−1
. With the current estimates, we get complexity close toO(n
3/2
) ford=3, roughlyO(n
8/3
) ford=4, andO(n
d−1−a(d)
) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR
3 when the three sets are suitably separated.
A preliminary version of the results of this paper appeared in 16] and 17]. Part of this research by J. Matoušek was done
while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper
was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his
research was supported in part by NSF Grants CCR-8902522 and CCR-9111491. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|