Generalizing Ham Sandwich Cuts to Equitable Subdivisions |
| |
Authors: | S Bespamyatnikh D Kirkpatrick J Snoeyink |
| |
Institution: | (1) Department of Computer Science, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z4 besp@cs.ubc.ca, kirk@cs.ubc.ca, snoeyink@cs.ubc.ca , CA |
| |
Abstract: | 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.
Received February 19, 1999, and in revised form June 3, 1999. {\it Online publication August\/} 18, 2000. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|