Generalizing Ham Sandwich Cuts to Equitable Subdivisions
Generalizing Ham Sandwich Cuts to Equitable Subdivisions
复制标题
将火腿三明治推广到公平的细分
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
J. Snoeyink
中科院分区：
文献类型：
--
作者：
Sergei N. Bespamyatnikh;D. Kirkpatrick;J. Snoeyink
我们证明了一个推广的著名火腿三明治定理的平面。给定平面上一般位置的gn个红点和gm个蓝点，存在将平面均匀地细分为g个不相交的凸多边形，每个凸多边形包含n个红点和m个蓝点。当g = 2时，这个问题等价于平面上的火腿三明治定理。我们还提出了一个有效的算法来构建一个公平的细分。
We prove a generalization of the famous Ham Sandwich Theorem for the plane. Given gn red points and gm blue points in the plane in general position, there exists an equitable subdivision of the plane into g disjoint convex polygons, each of which contains n red points and m blue points. For g = 2 this problem is equivalent to the Ham Sandwich Theorem in the plane. We also present an efficient algorithm for constructing an equitable subdivision.