The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
2라고 가정m 빨간색 점과 2n 격자에 파란색 점이 표시됩니다. Z2 비행기에서 R2. 우리는 그들이 일반적인 위치에 있다면, 즉 각 수직선과 수평선에 최대 하나의 점이 있다면 빨간색 점과 파란색 점을 모두 이등분하는 직사각형 절단이 존재한다는 것을 보여줍니다. 더욱이 일반적인 위치에 있지 않은 경우, 즉 일부 수직선과 수평선에 두 개 이상의 점이 포함될 수 있는 경우 빨간색 점과 파란색 점을 모두 이등분하는 반직사각형 절단이 존재합니다. 우리는 또한 이러한 결과가 어떤 의미에서 가장 가능하다는 것을 보여줍니다. 더욱이, 우리의 증거는 다음과 같습니다. O(N 기록 N), N=2m+2n, 원하는 컷을 찾기 위한 시간 알고리즘.
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.
부
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 2m red points and 2n blue points are given on the lattice Z2 in the plane R2. 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.502/_p
부
@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 2m red points and 2n blue points are given on the lattice Z2 in the plane R2. 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.},
keywords={},
doi={10.1587/transfun.E92.A.502},
ISSN={1745-1337},
month={February},}
부
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 2m red points and 2n blue points are given on the lattice Z2 in the plane R2. 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.
ER -