kano

Information about kano

Published on September 18, 2007

Author: Seasham

Source: authorstream.com

Content

Non-crossing geometric path covering red and blue points in the plane :  Non-crossing geometric path covering red and blue points in the plane Mikio Kano Ibaraki University Japan October 2002 Slide2:  R=a set of red points in the plane={ } B=a set of blue points in the plane={ } We always assume that no three points in R U B lie on the same line. Slide3:  Theorem If |R|=|B|, then there exists a perfect non-crossing geometric alternating matching that covers R U B. Slide4:  Proof of the previous theorem by using Ham-sandwich and by induction f(n)=2f(n/2)+O(n) f(n)=O(n log n) Slide5:  Problem For given RUB, can it be covered by geometric alternating paths Pn of order n without crossing ? = =8 Path P4=Pn Slide6:  When we consider paths of odd order, the number of red points might not be equal to the number of blue points. =2.3+1.2=10 =1.3+2.2=7 Path P3=Pn Theorem (Kaneko, MK, Suzuki):  Theorem (Kaneko, MK, Suzuki) If |R|=|B|=km and 2m andlt;=14, then RUB can be covered by path P2m without crossings. If |R|=k(m+1)+hm, |B|=km+h(m+1) and 2m+1 andlt;=11, then RUB can be covered by P2m+1 without crossings. 2,3, …,11,12,14 are OK. 13,15,16,… NO Sketch of Proof (I):  Sketch of Proof (I) We show that there exist a balanced convex subdivision of the plane such that each convex polygon contains either 2m red+blue points or 2m+1 red+blue points. If 2mandlt;=14 or 2m+1andlt;=11, then every configuration of 2m red+blue points or 2m+1 red+blue points has P2m or P2m+1 covering without crossings. In other case, there exists a configuration having no Pn coverings. Slide9:  Sketch of Proof II Step 1: Convex balanced subdivision of the plane Step 2: For each subdivision, there exists a non-crossing path P6 |R|=|B|=18 Slide10:  P5 |R|=3*4+2*2=16, |B|=2*4+3*2=14 Slide11:  2m+1=13 We show some configurations which have no path covering. Slide12:  2m=14 Slide13:  2m+1=15 Slide14:  2m+1=16 Slide15:  2m+1=17 Slide16:  2m+1=18 Balanced convex subdivision of the plane:  Balanced convex subdivision of the plane 2m=6 Slide18:  Theorem (Bespamyatnikh, Kirkpatrick,Snoeyink, Sakai and Ito, Uehara,Yokoyama) If |R|=ag and |B|=bg, then there exists a subdivision X1 U X2 U … U Xg of the plane into g disjoint convex polygons such that every Xi contains exactly a red points and b blue points. Slide19:  An equitable subdivision of 2g red points and 4g blue points. Not convex n^(4/3) (log n)^3 log g time algorithm Slide20:  Applying the above theorem with a=b=m to our RUB, we can obtain the desired convex subdivision of the plane. Namely, if |R|=|B|=km, then there exists a subdivision X1U … UXk of the plane into k disjoint convex polygons such that every Xi contains exactly m red points and m blue points. Slide21:  Theorem (Kaneko, MK and K.Suzuki) If |R|=(m+1)k+mh and |B|=mk+(m+1)h, then there exists a subdivision X1 U … U Xk U Y1 U … U Yh of the plane into k+h disjoint convex polygons such that every Xi contains m+1 red points and m blue points, and every Yj contains m red points and m+1 blue points. Slide22:  m=2 and m+1=3 Slide23:  We can prove the above theorem in the same way as the proof by Bespamyatnikh, Kirkpatrick, Snoeyink. However we generalize the key lemma as follows. The proof is the same as the proof given by the above people. Slide24:  Three cutting Theorem Let |R|=g1+g2+g3 and |R|=h1+h2+h3. Suppose that for every line l with |left(l) R|=gi, it follows that |left(l) B|andlt;hi. Then there exists three rays r1, r2 and r3 such that g3 red points and h3 blue points g1 red points and h1 blue points g2 red points and h2 blue points r1 r2 r3 Slide25:  less than h1 blue points g2 red points g3 red points less than h3 blue points Conditions of 3-cutting Theorem g1 red points less than h2 blue points Slide26:  h1 blue points g2 red points g3 red points A balanced convex subdivision A vertical line g1 red points h2 blue points h3 blue points Not convex Remark on the above theorem:  Remark on the above theorem Let a and b be integers s.t. 1andlt;=a, a+2andlt;=b. Then there exist configurations of |R|=ak+bh red points |B|=bk+ah blue points for which there exist no convex balanced subdivisions of the plane. Thus the above theorem cannot be generalized. Slide28:  a=2, b=4 Each polygon contains either 2 red points and 4 blue points, or 4 red points and 2 blue points. Slide29:  P4 We finally show that if either |R|=|B| and |R U B|andlt;=14, or |R|=|B|+1 and |R U B|andlt;=11, then R U B can be covered by Pn. |R U B|=4 Slide30:  P5 |R U B|=5 Slide31:  P6 |R U B|=6 Slide32:  Lemma |RUB|=5. If RUB is a configuration given in the figure, there exists a path P5 which covers RUB and starts with x. x Bad case A new line satisfies good condition. |R U B|=9 Slide33:  Lemma |RUB|=6. If a red point x can see a blue convex point y, then there exists a path P6 which covers RUB and starts with x. x y We can show that we may assume that there exits a line in the figure. |R U B|=11 Conjecture (A.K, M.K):  Conjecture (A.K, M.K) Let g=g1+g2+ … +gk such that each gi andlt; g/3. If |R|=ag and |B|=bg, then there exists a subdivision X1 U X2 U … U Xk of the plane into k disjoint convex polygons such that each Xi contains exactly agi red points and bgi blue points. Xi agi red points bgi blue points Find a nice problem from the following figure, and solve it:  Find a nice problem from the following figure, and solve it Thank you

Related presentations


Other presentations created by Seasham

IBM
18. 09. 2007
0 views

IBM

CHEER LEADING
18. 06. 2007
0 views

CHEER LEADING

FJP
18. 09. 2007
0 views

FJP

14 ZIMBABWE Country Report
18. 09. 2007
0 views

14 ZIMBABWE Country Report

alphabetuppercase
18. 09. 2007
0 views

alphabetuppercase

Stewart Paulson
18. 09. 2007
0 views

Stewart Paulson

Conf2004 Consultant Smith MAI
18. 09. 2007
0 views

Conf2004 Consultant Smith MAI

03 Pole Mer
18. 09. 2007
0 views

03 Pole Mer

GCC2002 G JavaMPI
18. 09. 2007
0 views

GCC2002 G JavaMPI

Blue Whales
18. 09. 2007
0 views

Blue Whales

RDFIntro
18. 09. 2007
0 views

RDFIntro

All About Whales power point
18. 09. 2007
0 views

All About Whales power point

upload
18. 09. 2007
0 views

upload

vendor meeting 20051207
18. 09. 2007
0 views

vendor meeting 20051207

Complexity
18. 09. 2007
0 views

Complexity

BC 101 revised 2007
18. 09. 2007
0 views

BC 101 revised 2007

ossia
18. 09. 2007
0 views

ossia

palais 06
18. 09. 2007
0 views

palais 06

ibm stockholm
18. 09. 2007
0 views

ibm stockholm

Iron Overload Wells
18. 06. 2007
0 views

Iron Overload Wells

IPC Solutions Praesentation
18. 06. 2007
0 views

IPC Solutions Praesentation

D203 Sauers
18. 06. 2007
0 views

D203 Sauers

Concussion in Sports
18. 06. 2007
0 views

Concussion in Sports

colons
18. 06. 2007
0 views

colons

apostrophe
18. 06. 2007
0 views

apostrophe

istorija
18. 06. 2007
0 views

istorija

Creation of an Ancient Newspaper
15. 06. 2007
0 views

Creation of an Ancient Newspaper

coniferous Trees
15. 06. 2007
0 views

coniferous Trees

communities
15. 06. 2007
0 views

communities

columbus
15. 06. 2007
0 views

columbus

colorful utah
15. 06. 2007
0 views

colorful utah

chicks
15. 06. 2007
0 views

chicks

IR REBULL05
18. 06. 2007
0 views

IR REBULL05

1st Lego League presentation
18. 06. 2007
0 views

1st Lego League presentation

kincaid
18. 09. 2007
0 views

kincaid

introductory
18. 06. 2007
0 views

introductory

DITA Briefing3
18. 09. 2007
0 views

DITA Briefing3

bryllups invitasjon
18. 06. 2007
0 views

bryllups invitasjon