| Presentation | 2001/9/7 Geometric Alternating Path-Covering and its Polynomial Time Algorithm Mikio KANO, Atsushi KANEKO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We prove that for given ag+(a+1)h red points and (a+1)g+ah blue points in the plane in general position, There exists a subdivision X_1U…UX_gUY_1U…UY_h of the plane into g+h disjoint convex polygons such that every X_i contains a red points and a+1 blue points and every Y_j contains a+1 red points and a blue points. We also prove that for given 2g+1(≩5) red points and (2g+1)b blue points in the plane in general position, there exists a subdivision X_1UX_2U…UX_g of the plane into g+1 disjoint convex polygons such that X_1 contains one red point and b blue points and every other X_i(2&InE;i&InE;g+1) contains two red points and 2b blue points. Our proofs give polynomial time algorithms for finding the above two subdivisions. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Geometric Alternating Path / Balanced subdivision / two sets of points in the plane |
| Paper # | COMP2001-29 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2001/9/7(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Geometric Alternating Path-Covering and its Polynomial Time Algorithm |
| Sub Title (in English) | |
| Keyword(1) | Geometric Alternating Path |
| Keyword(2) | Balanced subdivision |
| Keyword(3) | two sets of points in the plane |
| 1st Author's Name | Mikio KANO |
| 1st Author's Affiliation | Faculty of Engineering, Ibaraki University() |
| 2nd Author's Name | Atsushi KANEKO |
| 2nd Author's Affiliation | Faculty of Engineering, Kogakuin University |
| Date | 2001/9/7 |
| Paper # | COMP2001-29 |
| Volume (vol) | vol.101 |
| Number (no) | 307 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |