On Covering Problems of RadoSergey BeregUniversity of Texas at DallasAdrian DumitrescuUniversity of Wisconsin - MilwaukeeMinghui JiangUtah State UniversitySWAT July 2–4, 2008A Conjecture by T. Rado in 1928For any set S of axis-parallel squares in the plane, there isalways a subset I of pairwise disjoint squares such thattotal area of squares in Iis at least 1/4 ofunion area of squares in SMore Precisely...For a finite set S of convex sets in Rd, the union volume (orunion area when d = 2) of S is|S| = | ∪C∈SC|.For a convex set S in Rd, defineF (S) = infSsupI|I||S|,where S ranges over all finite sets of convex sets in Rdthat arehomothetic to S, and I ranges over all independent subsets of S.Is it true that F (S) ≥ 1/4 for a square S?Upper BoundF (S) ≤ 1/4Lower BoundF (S) ≥ 1/9Greedy algorithm: largest first (T. Rado 1928)F (S) ≥ 1/8.6Semi-greedy algorithm: largest or neighbors (Zalgaller 1960)The QuestionF (S)?= 1/4Disproved by Ajtai in 1973(b)(a) (c)S4S1S3S2R2R4R1R3(a) A system of 4 squares.(b) An ambiguous system of 13 squares.(c) Ajtai’s construction shown schematically: F (S) < 1/4.Our ResultsFor a square S,1/8.6 < 1/8.4797 . . . ≤ F (S) ≤ 1/4.0421 . . . < 1/4.Improved F (S) bounds for disks, centrally symmetric convexsets in R2, arbitrary convex sets in R2, and hypercubes in Rd.Improved f(S) bounds for congruent convex sets in R2.Improve Upper BoundEstimate of Ajtai 1973:1/4 − 1/1728 = 1/4.0092 . . .Our result:1/4 − 1/384 = 1/4.0421 . . .Improve Ajtai’s System(b)(a) (c)S4S1S3S2R2R4R1R3Step 1: design a better gadget RStep 2: repeat the system in a tiling(a)Z1Z2Rbacdf ge hC4C3C2C1B1B4B3B2A1A2A3A4A5A6A7A13A12A11A10A9A8A14A15A17A16A19A18A20A21A22A23SSS S(b)(d)(c)(a)(c)(b)S1S2S3S4Improve Lower BoundT. Rado 1928 (largest first): 1/9R. Rado 1949 (largest or two neighbors): 1/8.75Zalgaller 1960 (largest or at most four neighbors): 1/8.6Our results:largest or two neighborsor two neighbors of a neighboror two neighbors of a neighbor of a neighbor...1/8.5699 . . .largest or three large neighbors1/8.4797 . . .Algorithm A1• S = {S1, . . . , Sn} is a set of axis-parallel squares.• Tiis the smallest axis-parallel square that contains all squaresin S that intersect Si.• xiis the side length of Si.• yiis 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.Selection Round of Algorithm A11. Find the largest square Slin S.Assume without loss of generality that xl= 1.2. If yl≤√λ, add Slto I, delete from S the squares thatintersect Sl, then return. Otherwise, set k ← l and continuewith the next step.3. Let Siand Sjbe two squares that intersect Skand touchtwo opposite sides of Tk. If both ziand zjare at most zk,add Siand Sjto I, delete from S the squares that intersectSior Sj, then return. Otherwise, set k ← i or j such thatzkincreases, then repeat this step.The idea: keep searching if a neighbor has “more” neighbors.In Every Iteration of Step 3Since Siand Sjare two squares that intersect Skand touchtwo opposite sides of Tk,xi+ xj+ xk≥ yk= xk+ zk.Then,xi+ xj≥ zk.So when we reach the last iteration of Step 3...|Ti∪ Tj||Si| + |Sj|=|Ti| + |Tj| − |Ti∩ Tj||Si| + |Sj|≤(xi+ zk)2+ (xj+ zk)2x2i+ x2j−x2kx2i+ x2j= 1 +2zk(xi+ xj) + 2z2kx2i+ x2j−x2kx2i+ x2j≤ 1 +2zk(xi+ xj) + 2z2k(xi+ xj)2/2−(√λ − 2)22= 1 +4zkxi+ xj+4z2k(xi+ xj)2−(√λ − 2)22≤ 9 − (√λ − 2)2/2Two Cases1. If Slis selected (in Step 2),|Tl||Sl|≤ λ.2. If Siand Sjare selected (in the last iteration of Step 3),|Ti∪ Tj||Si| + |Sj|≤ 9 − (√λ − 2)2/2.9 − (√λ − 2)2/2 = λλ = (√46 + 2)2/9 = 8.5699 . . .F (S) ≥ 1/λ for a square S.More Lower Bounds3d− (λ1/dd− 2)d/2 = λdF (S) ≥ 1/λdfor a hypercube S in Rd.SkSjSititjsisjF (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 A21. Let S0be the largest square in S.Assume without loss of generality that S0is a unit square.Let S0⊆ S \ {S0} be the set of squares of side length atleast s = 0.8601 . . . that intersect S0.2. If S0contains three disjoint squares S1, S2, and S3, thenadd S1, S2, and S3to I. Otherwise add S0to I.3. For each square Siadded to I, remove from S the squaresthat intersect Si.The idea: take the largest or three large neighbors.Two CasesS0S3S2S11111111S0(b)(a)8 + 3s2+ 10s3s2= 7 + 2s2= 8.4797 . . .SummaryFor a square S,1/8.6 < 1/8.4797 . . . ≤ F (S) ≤ 1/4.0421 . . . < 1/4.Improved F (S) bounds for disks, centrally symmetric convexsets in R2, arbitrary convex sets in R2, and hypercubes in Rd.Improved f(S) bounds for congruent convex sets in R2.Thank
View Full Document
Unlocking...