區(qū)域覆蓋問題

1、圓覆蓋矩形區(qū)域問題給定一個MXN的矩形區(qū)域，現(xiàn)用半徑為,的圓對其進(jìn)行完全覆蓋,要求相鄰兩個圓相交的公共面積不小于一個圓面積的k%，則應(yīng)如何覆蓋可使得完全覆蓋整個圖形時所用圓的個數(shù)最少（注：如果一個圓只有部分在圖形中，也按一個計算）?例如，設(shè)M=N=1000、r=100，貝1當(dāng)k=5和k=18時，結(jié)果如何?是否有一般性結(jié)論?摘要：本文利用了分類討論思想方法，對如何合理地用圓對矩形區(qū)域進(jìn)行覆蓋的問題進(jìn)行了有效的分類討論，使得對矩形區(qū)域進(jìn)行完全覆蓋所用圓的個數(shù)最少。其次，利用了由一般及特殊的方法，先得出一般結(jié)果,從而歸納分類總結(jié)出一般規(guī)律，進(jìn)而得出結(jié)論。再次，對于這一問題，采用了先鋪圓再放矩形的方式

2、。最后，將矩形進(jìn)行了一系列平移，發(fā)現(xiàn)當(dāng)矩形的一些邊與圓與圓的相交弦重合時最優(yōu)；而對于圓的放置，首先選擇了放置相交面積相等的圓，從而又發(fā)現(xiàn)，對于中間每個圓的所有弦形成的多邊形恰為正多邊形.最后，由相交圓的面積滿足不小于k%可以找到相應(yīng)的多邊形對應(yīng)的邊數(shù)。關(guān)鍵詞：矩形區(qū)域圓覆蓋1、問題重述:給定一個MxN的矩形區(qū)域，現(xiàn)用半徑為r的圓對其進(jìn)行完全覆蓋，要求相鄰兩個圓相交的公共面積不小于一個圓面積的k%。1、怎應(yīng)如何覆蓋可使得完全覆蓋整個圖形時所用圓的個數(shù)最少（注：如果一個圓只有部分在圖形中，也按一個計算）？2、設(shè)M=N=1000,r=100,貝當(dāng)k=5和k=18時，結(jié)果如何？3、是否有一般性結(jié)論？2

3、，模型的假設(shè)與符號說明：1.模型假設(shè)：.圓與圓的相交面積相同（即相交弦長相等）.當(dāng)圓部分在矩形區(qū)域中時，仍算一個圓.圓環(huán)系中的弦與矩形的某些邊時重合的，若不重合我們也可以經(jīng)過簡單的平移，使得矩形的某些邊與弦線重合2.符號：每個圓的半徑r0=0=2兀n最小相交圓面積占整個相k交圓面積的百分比矩形的長M矩形的寬N正多邊形的邊數(shù)n每條弦所對應(yīng)的圓心角0每條弦的弦長x弦到圓心的距離d覆蓋矩形所需圓的個數(shù)Mpq，p為列個數(shù)，q為行個數(shù)弦所對應(yīng)的弧長l扇形面積S扇三角形面積S三角相交圓面積S相交3。模型的建立與求解1，圓的弦所對應(yīng)的圓心角2，弦與圓心角關(guān)系l=er3，扇形面積S=1Ir扇24,三角形面積1

4、S=r2Sino三角25,相交面積相交相交k%兀r26，對于相交面積的關(guān)系s扇s三角-2s相交將以上式子整理即可得到：1k%Kr1k%Kr22-rr-r2Sm2nr2n2兀2兀Sink%兀即：nrnr而對于一個相當(dāng)大的矩形區(qū)域我們對其劃分,將其劃分為很多個正多邊形。則這些正多邊形應(yīng)該具有剛好不重合地覆蓋完整個矩形區(qū)域（對于邊界上的正多邊形我們可不做要求剛好覆蓋）。而對于正多邊形的邊數(shù)我們發(fā)現(xiàn)：引理1在將矩形劃分成正多邊形中,正多邊形能且只能是正三角形、正四邊形和正六邊形.現(xiàn)在我們來證明引理1:證明：設(shè)在劃分矩形為正n邊形且n3,正n邊形的每個內(nèi)角TOC o 1-5 h z_180(n-2)36

5、0ax=值為a，顯然n，我們設(shè)a(x3,xeN*)，貝2n2x4xnn2+n-2x-2x-2解方程得：x3，n6;x4,n4;x6,n3。即:在將矩形劃分成正三角形中只可能是正三角形、正四邊形、正六邊形，因此,應(yīng)選擇正三角形、正四邊形或正六邊形拼接矩形區(qū)域.現(xiàn)在我們對n取不同值時，討論k的臨界值：方案一：當(dāng)用正三角形劃分矩形,即n=3時TOC o 1-5 h z2兀2兀-Sink%兀3解出臨界點:k1=39.1002方案二：當(dāng)用正四邊形劃分矩形即n=4時2兀2兀-Sink%兀4解出臨界點：k2=18。1690方案三：當(dāng)用正六邊形劃分矩形，即n=6時2兀2兀Sink%兀-6-6解出臨界點：k3=

6、5。7669故而：kkk1.當(dāng)21時，我們選擇用正三角形來劃分矩形，所用正三角形的個數(shù)即為覆蓋矩形所用最少圓的個數(shù)。kkk2。當(dāng)k3kk2時，我們選擇用正四邊形來劃分矩形，所用正四邊形的個數(shù)即為覆蓋矩形所用最少圓的個數(shù)。3.當(dāng)0kk%兀2兀-Sin2兀（、nn+1n+1（nN*）對于完全覆蓋MXN矩形圓個數(shù)的計算kkN(m-1)x/2r其中meN*,j=1,2,3,.qpj、pjpp解出W2.NmM(m-1)iq飛解出/2MmNmpjr+r+r+2r+r+2r+2r+r且m為奇數(shù)pjV2+、：2+3r2+、：2+3r+2N2J2r解出：3r+2-2；2rmM(m一1)iq為奇數(shù)，i=1,2,3

7、,.p)解出m解出mNm.pjTOC o 1-5 h z HYPERLINK l bookmark66 1-1r+r+r+2r+rHF2r+r+r+r且m為偶數(shù)FFpj HYPERLINK l bookmark68 0VX)(m-1).pj解出:2r+2NJ2r4-0+2r+2NJ2r解出:3rpj-3-3r,m故，,m故，pj_2r+2N-平r3r且mpj為偶數(shù)所以用偶數(shù)行可以覆蓋時，即p為偶數(shù)，此時總的個數(shù)為：xmpqpj(2i-1)qpj2iqC=1,2,.p;j=1,2,.q)4對于當(dāng)M=N=1000,r=100,貝口當(dāng)k=5時，我們選擇方案三計算，可得出所用總圓個數(shù)最少經(jīng)驗證p為奇數(shù)

8、，故有mpjmpj_3r+2N-2Fr且mpj為奇數(shù)3x1003x100+2x1000-2、/2x1003x100p為奇數(shù)=7而經(jīng)簡單計算得，偶數(shù)行的列數(shù)為8,而奇數(shù)行的列數(shù)為7所以：總的個數(shù)為：m=mxm+mxmpqpj(2i-1)qpj2iqG=1,2,P；j=1,2,.4)7x4+8x3=52k=18時，我們選擇方案二計算，可得出所用總圓個數(shù)最少一Z2100010加右m*=8故而pj丁3U0-/21000-o存根=7一，、=8叩iqTTUTm=mxm=8x8=64個所以：pqpjiq如圖：5，模型的推廣此模型針對不同的k值做出了不同的討論，最后得出一般結(jié)論：當(dāng)kk3時，用正六邊形來劃分矩形區(qū)域，當(dāng)kkk一,一,一、fkkk3kk2時，用正四邊形來劃分矩形區(qū)域，當(dāng)2時,是不存在這樣的劃分，即不存在這樣的覆蓋。而對于不等分隔圓時，我們可以由MxN來確定后進(jìn)行每個相鄰圓間相交面積相應(yīng)的增調(diào)整，得出一般性規(guī)律。6，模型評價在求解區(qū)域覆蓋時，對正三角性，正方行，正六邊形的區(qū)域覆蓋問題進(jìn)行了討論。在解決多邊行等邊界復(fù)雜圖形時問題,遇到了一定的困難。在討論時,運用編程作圖相對比較麻煩。用幾何