Name
Abstract | ||
|---|---|---|
Assume that 2m red points and 2n blue points are given on the lattice Z(2) in the plane R-2. We show that if they are in general position, that is, if at most one point lies on each vertical line and horizontal line, then there exists a rectangular cut that bisects both red points and blue points. Moreover, if they are not in general position, namely if some vertical and horizontal lines may contain more than one point, then there exists a semi-rectangular cut that bisects both red points and blue points. We also show that these results are best possible in some sense. Moreover, our proof gives O(N log N), N = 2m + 2n, time algorithm for finding the desired cut. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1587/transfun.E92.A.502 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
red point, blue point, lattice, bisector, rectangular cut, semi-rectangular cut, two sets of points | Linear separability,Horizontal and vertical,General position,Combinatorics,Lattice (order),Horizontal line test,Geometry,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
E92A | 2 | 1745-1337 |
Citations | PageRank | References |
1 | 0.39 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Miyuki Uno | 1 | 10 | 2.19 |
| Tomoharu Kawano | 2 | 1 | 0.39 |
| Mikio Kano | 3 | 548 | 99.79 |