Upper Bound On Covering Problems of Rado Sergey Bereg University of Texas at Dallas Adrian Dumitrescu University of Wisconsin Milwaukee Minghui Jiang Utah State University SWAT July 2 4 2008 F S 1 4 A Conjecture by T Rado in 1928 Lower Bound For any set S of axis parallel squares in the plane there is always a subset I of pairwise disjoint squares such that total area of squares in I is at least 1 4 of F S 1 9 Greedy algorithm largest first T Rado 1928 union area of squares in S F S 1 8 6 Semi greedy algorithm largest or neighbors Zalgaller 1960 More Precisely The Question For a finite set S of convex sets in Rd the union volume or union area when d 2 of S is S C S C For a convex set S in Rd define F S inf sup S I I S where S ranges over all finite sets of convex sets in Rd that are homothetic to S and I ranges over all independent subsets of S Is it true that F S 1 4 for a square S F S 1 4 Disproved by Ajtai in 1973 Improve Ajtai s System R1 a b R1 S1 S2 S4 S3 R2 c a R4 b S1 S2 S4 S3 c R4 R3 a A system of 4 squares b An ambiguous system of 13 squares c Ajtai s construction shown schematically F S 1 4 R3 Step 1 design a better gadget R Step 2 repeat the system in a tiling Our Results R C1 C2 b c a d B2 B1 For a square S a S C3 B3 C4 f g e h B4 S b 1 8 6 1 8 4797 F S 1 4 0421 1 4 Z1 Improved F S bounds for disks centrally symmetric convex sets in R2 arbitrary convex sets in R2 and hypercubes in Rd 2 Improved f S bounds for congruent convex sets in R Z2 c S A1 A2 A7 A8 A3 A9 S d Improve Upper Bound a Estimate of Ajtai 1973 1 4 1 1728 1 4 0092 Our result 1 4 1 384 1 4 0421 c S1 S2 S4 S3 b A4 A5 A10 A11 A6 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21 A22 A23 R2 Improve Lower Bound T Rado 1928 largest first 1 9 R Rado 1949 largest or two neighbors 1 8 75 Zalgaller 1960 largest or at most four neighbors 1 8 6 In Every Iteration of Step 3 Since Si and Sj are two squares that intersect Sk and touch two opposite sides of Tk Our results largest or two neighbors or two neighbors of a neighbor or two neighbors of a neighbor of a neighbor xi xj xk yk xk zk Then xi xj zk 1 8 5699 largest or three large neighbors So when we reach the last iteration of Step 3 1 8 4797 Algorithm A1 S S1 Sn is a set of axis parallel squares Ti is the smallest axis parallel square that contains all squares in S that intersect Si xi is the side length of Si yi is the side length of Ti zi yi xi is a constant will be set to 8 5699 To construct an independent set I initialize I to be empty then repeat the following selection round until S is empty Ti Tj Si Sj Ti Tj Ti Tj Si Sj xi zk 2 xj zk 2 x2k x2i x2j x2i x2j x2 2zk xi xj 2zk2 2 k 2 2 2 xi xj xi xj 2 2zk xi xj 2zk 2 2 1 xi xj 2 2 2 2 4zk 2 2 4zk 1 2 xi xj xi xj 2 2 9 2 2 1 Selection Round of Algorithm A1 1 Find the largest square Sl in S Assume without loss of generality that xl 1 2 If yl add Sl to I delete from S the squares that intersect Sl then return Otherwise set k l and continue with the next step 3 Let Si and Sj be two squares that intersect Sk and touch two opposite sides of Tk If both zi and zj are at most zk add Si and Sj to I delete from S the squares that intersect Si or Sj then return Otherwise set k i or j such that zk increases then repeat this step The idea keep searching if a neighbor has more neighbors Two Cases 1 If Sl is selected in Step 2 Tl Sl 2 If Si and Sj are selected in the last iteration of Step 3 Ti Tj 9 2 2 2 Si Sj 9 2 2 2 46 2 2 9 8 5699 F S 1 for a square S More Lower Bounds 1 d 3d d For a square S 2 d 2 d 1 8 6 1 8 4797 F S 1 4 0421 1 4 F S 1 d for a hypercube S in Rd sj si ti Summary Improved F S bounds for disks centrally symmetric convex sets in R2 arbitrary convex sets in R2 and hypercubes in Rd tj Improved f S bounds for congruent convex sets in R2 Sj Si Sk F S 1 8 5699 for a centrally symmetric convex set in R2 F S 1 8 3539 for a disk by a tighter analysis Selection Round of Algorithm A2 1 Let S0 be the largest square in S Assume without loss of generality that S0 is a unit square Let S0 S S0 be the set of squares of side length at least s 0 8601 that intersect S0 2 If S0 contains three disjoint squares S1 S2 and S3 then add S1 S2 and S3 to I Otherwise add S0 to I 3 For each square Si added to I remove from S the squares that intersect Si The idea take the largest or three large neighbors Two Cases 1 1 S3 1 S2 S0 S0 1 a b S1 1 1 1 8 3s2 10s 7 2s2 8 4797 3s2 Thank you
View Full Document
Unlocking...