版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、Chapter 4 Partition(1) ShiftingDing-Zhu Du汽車防盜器 zg001gps.Disk CoveringGiven a set of n points in the Euclidean plane, find the minimum number of unit disks to cover the n given points.(x,x)Partition P(x)a.Construct Minimum Unit Disk Cover in Each Cell1/2Each square with edge length1/2 can be covered
2、 by a unitdisk.Hence, each cell can be coveredBy at most disks. Suppose a cell contains ni points.Then there are ni(ni-1) possiblepositions for each disk.Minimum cover can be computed In time niO(a )2.Solution S(x) associated with P(x)For each cell, construct minimum cover.S(x) is the union of those
3、 minimum covers.Suppose n points are distributed into k cells containing n1, , nk points, respectively.Then computing S(x) takes timen1 + n2 + + nk nO(a )O(a )O(a )O(a )2222.Approximation AlgorithmFor x=0, -2, , -(a-2), compute S(x).Choose minimum one from S(0), S(-2), , S(-a+2).AnalysisConsider a m
4、inimum cover.Modify it to satisfy the restriction, i.e., a union of disk covers each for a cell. To do such a modification, we need to add some disks and estimate how many added disks. .Added DisksCount twiceCount four times2.2Shifting.Estimate # of added disksShifting.Estimate # of added disksVerti
5、cal stripsEach disk appearsonce.Estimate # of added disksHorizontal stripsEach disk appears once.Estimate # of added disks# of added disks for P(0)+ # of added disks for P(-2)+ + # of added disks for P(-a+2) 3 opt where opt is # of disk in a minimum cover.There is a x such that # of added disks for
6、P(x) (6/a) opt.Performance RatioP.R. 1 + 6/a 1 + when we choose a = 6 1/ .Running time is n.O(1/ )2.Unit disk graph15!.Each node can be charged at most 10 times!.Shifting3a/(2(h+1) = integerTime=nO(a )2h=2.Weighted Dominating SetGiven a unit disk graph with vertex weight, find a dominating set with
7、minimum total weight.Can the partition technique be used for the weighted dominating set problem?.Dominating Set in Intersection Disk GraphAn intersection disk graph is given by a set of points (vertices) in the Euclidean plane, each associated with a disk and an edge exists between two points iff two disks associated with
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024屆遼寧省東北育才、實驗中學(xué)高中畢業(yè)班第二次質(zhì)量檢測試題數(shù)學(xué)試題理試題
- 2024年科普知識生活常識知識競賽-科普知識競賽考試近5年真題集錦(頻考類試題)帶答案
- 2024年知識競賽-武漢船舶職業(yè)技術(shù)學(xué)院-起點杯知識競賽考試近5年真題附答案
- 2024年知識競賽-華創(chuàng)風(fēng)能風(fēng)機知識競賽考試近5年真題附答案
- 中班《一起來洗澡》課件
- 中班親子《樹枝裝飾藝術(shù)》課件
- 戶外娛樂場所安全保障工作總結(jié)計劃
- 年度發(fā)展目標與愿景計劃
- 新時代背景下的保安服務(wù)創(chuàng)新計劃
- 數(shù)據(jù)中心物理安全管理計劃
- 城市軌道交通列車自動控制系統(tǒng)維護 課件 2.8 車載應(yīng)答器天線維護檢修
- 2023年變頻電源行業(yè)市場突圍建議及需求分析報告
- 道法第二單元 成長的時空 單元測試 2024-2025學(xué)年統(tǒng)編版道德與法治七年級上冊
- 2024-2030年紙杯及紙容器行業(yè)市場現(xiàn)狀供需分析及投資評估規(guī)劃分析研究報告
- 時代樂章第一課城市名片 課件 2024-2025學(xué)年人教版(2024)初中美術(shù)七年級上冊
- 2024人教版道德與法治四年級上冊第三單元:信息萬花筒大單元整體教學(xué)設(shè)計
- 國慶75周年演講稿三
- 2024年秋季學(xué)期新滬粵版八年級上冊物理課件 第3章 光和眼睛第4節(jié) 光的折射規(guī)律
- 第10課《往事依依》公開課一等獎創(chuàng)新教學(xué)設(shè)計 統(tǒng)編版語文七年級上冊
- 早操觀摩評比活動方案與總結(jié)
- 清潔與衛(wèi)生刷牙(課件)一年級上冊勞動
評論
0/150
提交評論