The search functionality is under construction.

The search functionality is under construction.

Assume that 2*m* red points and 2*n* 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*=2*m*+2*n*, time algorithm for finding the desired cut.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.2 pp.502-507

- Publication Date
- 2009/02/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E92.A.502

- Type of Manuscript
- PAPER

- Category
- Algorithms and Data Structures

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Miyuki UNO, Tomoharu KAWANO, Mikio KANO, "Bisections of Two Sets of Points in the Plane Lattice" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 2, pp. 502-507, February 2009, doi: 10.1587/transfun.E92.A.502.

Abstract: Assume that 2*m* red points and 2*n* 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*=2*m*+2*n*, time algorithm for finding the desired cut.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.502/_p

Copy

@ARTICLE{e92-a_2_502,

author={Miyuki UNO, Tomoharu KAWANO, Mikio KANO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Bisections of Two Sets of Points in the Plane Lattice},

year={2009},

volume={E92-A},

number={2},

pages={502-507},

abstract={Assume that 2*m* red points and 2*n* 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*=2*m*+2*n*, time algorithm for finding the desired cut.},

keywords={},

doi={10.1587/transfun.E92.A.502},

ISSN={1745-1337},

month={February},}

Copy

TY - JOUR

TI - Bisections of Two Sets of Points in the Plane Lattice

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 502

EP - 507

AU - Miyuki UNO

AU - Tomoharu KAWANO

AU - Mikio KANO

PY - 2009

DO - 10.1587/transfun.E92.A.502

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E92-A

IS - 2

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - February 2009

AB - Assume that 2*m* red points and 2*n* 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*=2*m*+2*n*, time algorithm for finding the desired cut.

ER -