@# :
BidAUMIPA
SEMIRATA2OL4
BidangMIPA BKS-PTN.BATA
pangan, masalah "Integrasi sainsMIPAuntukmengatasi reklamasi, danlingkungan energi, kesehatan, 9-11Mei2014 IPBBaranangsiang, Center danKampus IPBInternational Convention
KOMPUTE& STATTSTTKA, DAN METEOROLOGT GEOFTSTKA STEM Alam Matematika danIlmu Pengetahuan Diterbitkan oleh:Fakultas Bogor InstitutPertanian
lllil llllillllllllllllllll til |tilt ilillllililllllllilllllilllilllllfl -0-9 tsBNs78-602-70491
M P A2 0 1 4J S E M I R A T A n idang 5 e m i n aNr a s i o n ad a nR r p a tT a h u n a E
PADAPOLYHEDRON POINT.GUARD PENEMPATAN ALGORITME ORTHOGONAL ON AN ORTHOGONAL FORPOINTGUARDPLACEIV]ENT AN ALGORITHIV POLYHEDRON Jefrilvlarzal Jamb P['llPAFK]PUniversilas (,m DaratJarnb].lefl-mafsal@vahoo l4endalo Karnpus ABSTRACT the rrumberor Art Galleryprobl€m(3DAGP)ams to deiermine The 3-Dimensional guardsr;quiredto coveran ad gallerythat ls modelledas an orthogonalpolvhedronas polyhedron.WhlLethere are ;/ell as the placementof these glards in lhe orthogonaL Problem little wotk has been Aft Gallerv extensiveresearcheson lhe 2_dimensiona the pointguard for detemining known algorithm is no done on the 3D-AGP.So far there p acemenlin whichthe guafd can be placesat anv positionto monitorthe inieriorof an arbitraryorihogonalpolyhedron.ln ihis paper,a methodis propos€diof point guafd placem;ntin orthogonalpolyhed|a.The key to lhis method s lhe mappingof the 3D Set Cover([/SC)problemThe nrelhodhaslhrcema]nsteps:(1) AGP lntoa l,4inimum prlsms'(2) conslruct decomposea givenorthogonalpolyhedfonlnto a set of rectangulaf a IVSCprobl€m (3) 3D-AGP inlo mapthe subsetfor eachcornerpoint,and a visibillty plzcement 3D'AGPand it guard's for the valid problern form a Any so utionto the MSC ca; be lnterpreiedas an upperboundof lhe numberof guardsto monitorthe odhogonal Atl galeryproblen,Mininun SetCavel Kewor.ls: Orthogonalpolyhedron, ABSTRAK ProblemArt Gallery 3 Dimensi(3D-AGP)beduiuanunluk menentukanjumlah glard yangdimodekansebagai suatuAit G3llery (penjaga)yang untukmengawasi dibutuhkan guad tersebut dalam guard penempatan maupun sebuah polyhedron orthogonal tentangpersoalanArt Gallery2 dimensisudahbanyak, polyhedronorthogonal.Penelitian akan tetapi sangatsedikitpenelitianpersoalanini secara3 dimensi Sejauhini belum ada algoiilme untuk menentukanpenempatanpoinlguard vaitu gu€rd yang dapat dlletakanpada sembarangposisipada sebuahpolyhedronorthogonaluntukmenronfior bagiandalamdari polyhedronorlhogonaltersebut.Dalampenelltianinl' sebuahmetode guarddalampolyhedronorthogonalKunc dai metodeinl diu;ulkanuntukpenempatan ]ni Set Cover([4sC) N4etode adalahmemetakan3D-AGPke dalampersoaan lMinimum sebuah polvhedron meniadi (1) orthogonal Partisi utama: mempunyai tiga langkah yang prismaoithogonal (2)Konstruk subsetdarihirnpunan prismao(hogonal, himpunan petakan AGP menjadi (3) 3D dapatleiihatdarisetisptitikpojokprismarectafguar,dan solLrsiuntukpersoalanlvlSCmeflrpakanso usi va ld bentukpersoalanl,4SC.Sembarang sebagabatasatas pointguardpada3D-AGPdan dapaidiinterpretasikan penempatan orthogona (upper-bound) untukmemontof suaiupolyhedron datit\rmlahpoint-guard SetCover Aft galleryprobiem l\4inimum Katakunci:Afthoganalpalyhedrcn, LATAR BELAKANG The Ad Gallery Problem(AGP) adaah persoalanklasik daanr geometri kan oleirVrctorKleepada T973kepada ini peftamakalidisampa komputasi. lvasaLah 3(6
"Berapabanyakpenlagaminmum yang mahasiswany. dal€mbeniuksebagaibeflkLrl: sehinggaseliaptilk dalam harusdilempatkardalamsuai! ealery sen sedemikian penjaga?" kurangnya saiu oleh sekurans [1] Sebuah salei lersebuldapatdlmofitor denah lanta biasanya lelapi galei seniefektifnya merup€kan sebLahsirukt!r3 dimensi, guard.Untukmenyederhanakan memberlkan ifformasiyangcukupunt!k penempatan yatu, persoalan, sebagaipoigonsederhana, suatugaleriseni basanyad modelkan yanstidakmemolong dirinya sendni[2] daerahyangdibatasi o eh .antaipoligon paoa1975,dlmana olehChavatal Solusipedamapersoaanqaleriini diberikan peniaga dan selalu memadaiuniuk kadangdibutuhkan bahwaL,l/31 dia membuktikan persoaan yangmempunyai , simplr1 sederhana meffonitor suatupoligon t3l. Semenjak dipelajai aslinyalelahdiusulkan ga erl senidimunculkan, banyakvaras daripersoalan jumlah yang guard dapat menlaga minimum menemukan a-61. Akan tetapi, 11, poligon adalahNP-hard ataupoligon orthogonal keseluruhan interior [7,8]. bahwa ouuine lantai Penelitianpada AGP pada awalnyamengasumsikan yang memonitorbangunan infonnasi rnemadai untuk rnemberikan sembarangbangunan yang inforrnasi tidak selau dapat membedkan tersebut.Akan teiapi,outlinetersebut Dengan memadaidenganstruklurruanganyang konrpleksdad suatu bangunansiruktur3 dinrensidai suatubangunan dem kian, sangatpenllnguntuknremperhatikan seniini sebagai penempatan guard.Kila menyeb!tversipersoalan Lrntuk menentukan the 3 DimensionalAn GalleryProblen l3D AGP),dlmanagaleriseni direpresentasikan oleh polyhedronorthogonal.Polyhedronorlhgonalmemberikanmodel sederhanatapi efektifdisebabkanoleh kenyataaanbahwakebanyakanbanqunandi dunia nvata dan orthogonal. galeriadalahkebanyakan berbentuk Peneliiiandalam 3D'AGP masih sedikit Bose et ai tgl dan Urrutiat5l menggunakannabileguad sepanlangrus!k rlrsuk unluk nremonitoreksterror polyhedron.aelakangan,Souvalne el a1 [10] memperkenalkanface 9uat.J: yailt) penjagaanyang befgerakdiseurlrh nieriors si dar polyhedronsedelhanadan mereka jumlahbalasatasmobileguardyangdlbLrtuhkan unluk juga menetapkan dan nremadal sederhana orthogonal polyhedron sede|hana danpolyhedroh interiof memonitof penlagaan Souvaine et a/.,penullsmengusulkan denganpenelilian Berlawanan polni{uar./ dan tidak tetap, poyhedron menggunakan o.thogonal lnterior sualLr penulis penelitian ini, mengusulkan guar.dyang bergerakDalam menggunakanan sebuah algoritmeuniuk menghilungpenempaianguad dlmana guard dapa\ po yhedron . padasembatang odhogona tiukdidalam dllempatkan PENDAHULUAN Terminologi poligonyangterbatas danterhLrbung, himpunan Polyhedron clidefin sikansebagai juga polgonlain poigon kepunyaan sebuah r!suk setap sehingga setap sedemikian polyhedron po yhed.on odhogonal Poligonpo igon ni dis€butdengansisi [1]1. Sualu dimanasetiaprusukparaleldengansalahsatusumbu didefnlsikansebagaipolyhedron kadesius 3 dimensi['i2j. sislemkoordinat orthgonal. Sisi emenpentingpoyhedron Sisi,rusuk,danslmpuladalahelemen-e polyhed.on poligon padapernr!kaan orlhogonal polyhedmn orthogonal orlhgonaladalah dimana3 alau lebilrsisl Slmpuladaah lilk paclapermlkaanpoyhedrofoathlgonal qans dimafaduasislbertenru. bertemLR!suk adalahse!men
Seminar Nasional danRapltTahunan a d.ngM PA2014I SEMIRATA Bentukpolyhedronyang komplekssering menjad alasanunluk membagi polyhedron tefsebulmenjadibentukyanglebihsederhana untukrnemrJdahkar oper€si operasr daanr poyhedronSalahsaluoperasipembagian tersebut adalahpartis,yallu prosesmembaglsuatupolyhedron yanglebihsederhana, odhosonal kedalamstrLrktur yang iidak berpotongan nrisalnyaprismareclangular, dengandklnyakecuallpada batasnya.Setiap pairlsi disebutdengan plece polyhedrcnorthgonalawal. Simbol Il digunakanuntuk mewakilikoleksi semua pima orthogonalyang dibuat dari pemparilisian polyhedron odhogonal. Unluk setiapprismarectangular, ierdapatdelapantilik pojck.Setiaptitik pojok berkorespondesi dengansimpulpolyhedron orthogoral,alau tiiik didaam interior polyhedronorthogonaltercebui.Jenistiiik pertamad sebutdengansimpuldanjenis iji k yang kedua disebut dengan iitik partisi. Gamb:r 1 nrenggambarkan polyhedron orthogorlalyang diparlisike dalarnhimpunanprismarectangular. Selelahpempadisian, yJ dan ,1 jlga utik pojok v7 adalah simpul, dan u1 adalahlitik parlisi.Masing-masing untuk prismafectangulafyangsama.Sebagaiiambahan,p da t', adalahbagiandatl partjsisi.
Gambar1 Pempadisian sebuahPolyhedron Odhogonal Sebuah penjagadapal ditempatkandi sebuahUtik terrentudalam po yhedron ofihogonal unluk memonitor interior polyhedron oftogonal. Setiap guard dapat memonitor sebagianinternalpolyhedron orthogonalUntukmemfasilitasi diskusi. isl ah berikutdipeftenalkan, dansebagian dianlarannya lelahdiperk€nalkan dalam1131. Definisi1. Dua titikx dan y dalampolyhedron orlhgonaP dikatakan dapalsaing garisxy yangtidakmemotong melihaljlka dan hanyajikalerdapat segnreni batasP. Deflnisi2. MisalkanP polyhedron orthogonaldan c adalahsebuahtitik P, daefahyang dapat dilihatdari c, dinyatakan denganV(c), adalahhimplnanUlikdalamP yang terlihat dadc. Definisi3. Bagianp dari P disebutterlihattolal dai cjika seliaptitikdari p tenihatdari c (yaitu,p s V(c)). p dikatakanterlihatsebagiandad c jika beberapa,tidak semua,lltik l e . f a ld a r i c . Dalamtulisanini, polrtguard diqunakansebagaiperyganliveftex
:r6u
I
Seidel memberikan sebuah conioh polyhedron orthogonal yane guatd ditempatkarpadasetiapsjmpultetap tidak b sa memonitorinteriorsecarslota . dan dia batas atas guard rnitimumuntuk memonitorpolvhedron kemudlanmemberjkan bahwa Q(n") guard d bullrhkandmana , adalah orthogona,dan menyatakan persoalan3-dimensuntuk banyaknyasimpu dalam po yhedron11l. Seanjutnya, pada polyhedron NP'hard[14] penjaga convex adalah minimum meletakan kedalam himpunanpnsma Suatu polyhedronol1hogonaldapat dipartsi prisma rectangula. reclanguiar sebagai pengganti tetahedra [15]. Jika setiap oithogonalakandimonitorsecara keseuruhanpolyhedron dialokaskansatupolhl-9ua,r.r, sebLrahguard pada seliappnsma penuh olehpoint-guard. Akan tetapi,menempatk3n padasebuah terlalLr berebihan.Sebuahguarddap6tditempatkan rectangular kelihatan kurangnya dua pnsma nremonitor sekurang panisi, conioh, akan sebagai titik jumlah minimurf titik adalah uniuk rnenemrrkan ini bertujuan reciangular.Penelitian total prisma reciangular dapat dimonitor secara sepertitersebutsehinggaseluruh diberikansemestapembicaraanU Dalampersoalanl\linlmumSet Cover([,4SC), dan himpunantak kosong S yang merupakansubset dari U. Tugasnya adalah U [16] Walaupun ka.dilitas minimumsubsetS' r: S yangdapatmelingkupi menemukan persoalanIVSCtelah dibuklikanNP-hard[16],ledapatbeberapasolusi praktisseperti backtmck. programinear,algoimagreedy, algoritme denganpendekalan ALGORITME PENEIlIPATAN POINT-GU4RD peniaga untLrk meletakan sebuahalgoritme Padabagianini,akandideskripsikan polyhedron berikutdigunakanuntuk pada sembarang orthogona.Langkah-langkah dr oeniaod: mengnasillan PenomPa prlsmarectangu ar. orihogonal ke dalamhimpLrnan Langkah1.Partsipolyhedron setiaplitikpoloksetiappismaorthogonal. Langkah 2. Bangunsubsetvisibilitas solusieksakaiau [./]SC daniemukan 3D AGPke persoalaf Langkah 3. Transformasikan penempaian persoa!an merupakan pendekatan NrlSC. Solusi tersebut untuk solusi penjagayangvalid. dalam[15] OperasipartisiyangcocokuntuklangkahLangkah1 ielahdibenkan Berikutnyakita akan fokus pada membangunsubsetvisibilitasyang dlbutuhkanpada unl!k Langkah 3. ke N4SC tmnfomasi3D-AGP Langkah 2 danmendeskripsisikan SubsetVisibilitas suatu subsetvisibiias adalahuntuk nrembangun Tujuandari penghltungan = = p p yanqtidakkosoig S { Srl/=7,,k }, dimanaE {/r l €n dan = V(g)} himpunan adalahsubsetvisibilitasuntukiitik pojokc,. subsetvislbllitas dari sebuahtitk pojokpisma seglProsedurpenghitungan enarrsisi i)setiapprlmaseq empatnremp!nyai observasi beikLrt: empatberdasarkan polyhedron dar dua iipe sisr TiDe I adaah sisl K€enamsisi ini dapaidlbag atas polyhedron odhogonal asalkecual dai titikinterior orthgonai asaldansislTipell berasal pada nrsuk-rusuk sisl.Jika rusukdai suatusisi adalahluga rusukdari poyhedron makatusLrk rusukTpe I Jika tidakdemikian, asal makarusukdikatakan odhogonal orthgonal aseldan disebrtdenganRusuk terdiridaritilikintedorsaja daripolyheCfon (prisma (vrcwpoiri),prismasesi-empat seg titk penqlihat Tipeil. (ii)UntuksetiapsualLr jka pefglihat daf hanya secaratota dai litik tersebutiika terlihat empatperiama)dapat
s€minar Nasional danRapat T.fun.nsidanp tltpA2014I SEMIRATA tidak terdapatprisma segi-empai dengansisi Tipe I beeotongandengangaris penghubung Utikpenglihatdengan peftan,a sebuahttittpadaprismarecatanguiar Algoritme yaogdibawahmensasumsikan kete.sediaan t;tlkpoiokc li=1,2, k) darimprimasegiempalrp)(J=1,2,., m) yangdihasitkan daripempartisian sebuah polyhedronodhogonal.Perhatikanbahwabeber-apa titik pojokdapatdipaka oteh tebih darisatuprisr.asegi-empat, sehingga k _<8m.Hal iniakanrnembuat k subsetvtsibittas 'S,(l=1, 2, . . . , k). Untukseliapliiikpojokakandipe ksaapakahsetiapprimasegi-empar dapat terlihatse&fa total dari titik pojok tersebutataLrtidak.Jika setiap titik dalam prismasegi-empaidapalterlihaldai titikpojok,makaprismasegiempatterseburlertihat secara total dari tilik pojok lercebut-Kalautidak, prismasegi empatterhatangsecara total atau sebagiandari litik pojoklersebut.Pada akhir pengulangan,S akan berisi sem!a prismasegiempatyangdapatledihat pojokq. LihatGambar secaratotaldarititik 2 untuklebihdetail. Frngsi lsviewBlocked (cambar3) mengambilsebuattitkcl, dan dua prismasegiempat,rptdan4orFungsiiniakanmempunyai nilaibaliklruejikapenglihatan darici ke rprdihambatdenganadanyarpr.Kalautidak,makafungsimempunyai nitajbatikFalse Untuk sembarangprismasegi,empatrpr dan litik c lerletakdituarrpj, terdapai antarasatu dan tiga sisi rpiyangdapalterlihatdad c, tergantung dariposisititik tersebul ke prismarectangualar. Sisiyangdapatterlihaiini dan tilik pojokdapaimembentuktiga piramidasegi'empat- piramidayang alasnyaberbentukpercegipanjang-, dengan setiapsisi yang dapal ie ihat padadasardan iitik pojokpada puncak.Jika prlsmasegi empallain rp menghambat penglihatan dad dari cke ry. baikseca€ totatataupun sebahagian, makaakanmemuatsekurang,kurangnya satusisiTipetatau rusLrk TipeL Kalau tidak prisma segi-empat /p, akan tefrliridari hanyalitk interiorsaia dad polyhedron orthogonal asal, dengan demiklan prisma seqiernpat tersebut akan Prismasegiempairp menghambat penglihatan daric ke rpijikadanhanyajika rprmemuat sisi Tipe I dan rusukTipe I yang berpoiongandengansalah satu piramida segr-empatyang telah disebutkandi atas Untukmetihatmengapaini menjadicondisi yangdiperlukan, misalkan diasumsikan bahwa/p tidakmenghampal pengtihatan dari ci ke 4oj.Hal ini berarti bahwaterdapatsekufangkurangnyasatu iitik s datamrpryang dihambaiolehrp. Garjsyangmenghubungkan c dans akanberpotongan dengansatu ataulebihtiUkrp. Salahsatudariperpolongan iniharustah teretakdatamsisiTtpeI atau rusuk Tipe l, karena jika tidak semua lillk perpotonganakan menjadi titik interior polyhedron rectangular asalyangkansaparan dan tidakmenghatangi pengtihalan Hal ini membuktikanbahwajika rp,mengharnbat pengtihatandari c,ke /p,. maka rp harus memuatsisi Tipe lat3u rusukTipelyang bepoiongandangansalahsatu ptrajnida rectangular. Untuk melihatkondisiini nremadai,kita hanya membutuhkan untuk mengarnbil sembarang Utikperpotongan s antarasisiTipeI rprdansaah satupiramida rectangulafKarenas te et€kdalampiranrda, garisciai c ke s dapatdtpeeanlang sampaike dasarpiramida, berakhir di titikt. Jelastahbahwatitikt pada sisi rprtidak dapatdilihaldaric, karenapenglihalan terhalang olehtitiks yangberadapadas si TipeI ataurusukT pe I rp. Haliniberanibahv/a rprmenghatafgi penglihatan danc ke rp
370
L
f o f ( i . 1 t o h ) { f o . ( j = I t o m ) i If (., is a co.nef poift of rpj) { 5 , - 5 t + { . P ' } , cantinue;
)
b L o . h e d= f a l t e , {o. (l = 1to r ){ if (L l=j ) b L o c h e d- I s v i e l s t a c k e d i . , , i+ | bLo.kett )
] it
rp), .p')t
( not bL..hed ) sj =s! | l rptlj
I
, subsitevisibiliias Gambar2 Agoritmepernbuatan function rrvie,BtocFed (.i,
{
.pj,
.p)
rdr edger base, re.tohgLa pyronid; fo. ( ,rse = each of the re.t.ngular if
fa.es of fpr that a.e visible
( base is a rype r face ) |etu.n trle; py.anid = the .€ctangular pyranid fo.ded by point .t for ( .e.tansle = each fa.e of rp1 ) { i t < r e c t a n g L ei s a r y p e I f a . e ) i+ (rectangLe intersects !ith prrdlid ){
from point
and .e.tangl€ bdsej
cls€ r€tuff false; for (edge = each of re.tanqLe s rype r edees) { if (€dqe inte.se.ts with PYrdmid) .eturn t.uej) J f€turn falsej)
untukmenentukanhambatan. Gambar3 FungsilsviewBlocked panjang dansuatupkar.idasegr-empat Unlukmenentukan apakahsuatupersegi satu samalain, seseorangdapatmemeriksaapakahsalahsatudari ernpal berpotongan titik pojok persegipanjangtenetakdalam pyr3mid.Jika salah satu dilemukandalam piramida,maka persegipanlangdan piramidaberpolongansatu denganyang lainnya. Jika tidak ada tilik pojok yang yang terletakdi dalam pramlda,kila r.asih perlu dimanasemuatitik mempeftatikan kasusketikapefsegipanjangmemotong..pirarr!da polok beradadi luar piramida.Hal ini denganmudah dapat diveilLkasi dengan pengamblsetiaprusuk pirarnidadan mellhetapakah saah ataL r!suk tersebut denganpercegipanjangJka salahsatlr rusukdtemukanberpotongan berpotongan satusa|ia denganpersegipanjang,makapyfamdadan percelipanjargbe,putu,,garr merekalidakbefpotongan salusamaiain la nnya.Dalamhallainnya 3D-AGPke dalamMasalahMSc Pemetaan orlhogonal P, asumskanbah,\iaP dlpadisike Diberikan sebuahpolyhedron yangterdlrldanrnprismareciengular ll = {p, p adaah prsma daiamsebuahhimpunan prosedur untLkmembangun k r:1,...,m). Subbab 3.T mendeskripsikan rectangular dan subsetvisibilitasSiU=1,2,,k),setiapsubsetmemuaipris,nareciar,llularyangterlhal
Rapatlahunan Sidang MIPA2014i SEMIRATA Semina. Naeionalda. secara total dai sebliah titik pojok yang diberikan.Penempatanguard irivial dapai diperolehdenganpenempaiansaiu guard pada setiaptrtikpoiok. Hal ini dikarenakan setiap guard dapat memonito.sejumlahprismaprismarectangulardan k guad alan menronitor semua prisma rectangularsehingga keseluruhaninteror polyhedron yaitu,9i bk Sr=[ = P. orthogonaltermonitor, Akan tetapi jumlah guard pada skema penempalantivial di atas teralu benebihan. Banyak prisma reciangulardapat lerlihat dari beberapa iitik pojok. Selanjutnyabeberapsubsetvisibilitasdapat bensikansemua pisma rectangulardati jika jumlahsubset jumlahguarddapatdikurangi subsetyanglain.Dengandemikian, visibilitasdapatditemukan. Karenasetiaptitik poiokcrmempunyaiasosiasidenganSl,tugas di atas ekivalen dengan,peffnasalahI\,4Sc-Dengan demikian permasalah3D-AGP problem dapat U: II dan S = {Sr Sr,...,Sk}Solusi ditransferke persoalanMSCdenganmentranformasi yaltu, subset S's S dengan kardinalitasminimumyang untuk permasalahanI\,4SC, melingkupin memberikankita penempatanguatd yang valid,dana kardinalitasdarj S' dapatdiinterpretasikan sebagaijumlahguarduntukP. KESIMPULAN sebagai Kompleksitaswaktuunluk algoritmepenempaianguard dikalkulasikan polyhedron orthogonalmenjadl be kut. Pertama,kompleksitaswakiu unluk membagi jumlah bidangpembagi,dan seluruhpartisi ditentukanoleh himpunanprjsmaorthogonal ,r, lomlah simpul dalam polyhedron dapat diselesaikan dalam waktu polynomial orthogonal-Kedua, subset visibilitasdapat d konstruksidalam O(m3) seperti vang ditunjukanpada seksisebelumnya.Dapatditetapkanbahwa m < ll3, dengandemikian n. Akan tetapi,langkah dalamwaktupolynomial subsetvisibiliias dapatdikonstruksi permasalah yaitu NP-hafd. Jadi, sebeEpapun [.4SC, akhif membutuhkan solusidari waktu secara kompleksitas kompleksitasdari partisidan konstruksisubsetvisibililas, penempatan guardmasihexponensial dalamrr. keseluruhan Walaupun menemukansolusi eksak p€rmasalahMSC adalah exponensial, ini dapat terdapat algoriime heuristic dan pendekatan[17]. Algodtrne-algoritme menghasilkansolusi yang mendekatisolusi yang sebenarnya.Sangat penting untuk diiegaskan bahwa walaupun penyelesaiandai permasalah [,'lSC adalah suetu penempalanguardyang valid. pendekatan, akantetapitetapmemberikan persoalan 3D-AGP m€njadipersoalanIMSC,tulisan ini Dengan transfomasi menunjukanpenempaiandan jumlah guar.l yang valid dalam polyhedronodhogonal sebagaibaias aias Jumlah Solusidari persoatanMSC tersebutdapatdiinterpretasikan guardunlukrnemonitor inleriorpolyhedron orlhogonal PUSTAKA [1] O'RourkeJ 19a7.Atl GalleryThearcnsandAlgarithms.OxfordUniversityPress. [2] Berg [.aD, Kreveld MV, Overmars M, schwazkopf O. 2AAo. Computationat GeomelrySeconded. Springer lheoremin planegeometry.ConbinatarialTheory Chavatal V. T975 A comblnatorial [3] Se/esA, vol.18,pp 39 41 of IEEE,pp 1384 in art galleries. in Proceedings lal ShemerTC.1992.Recentreslrlts 1399 372
l-
l5l Urrutia J. 2AOO.Art gattery and llluninationPrablems. Amsierdam:Elsevier probem presented al the ]n thead gaLlery [4azalJ. XieH. 2009.Guardsplacem€nt and ComputingSymposiuin,Peith ElectricalEnglneering The 1oth Postgraduate of ar1galleryproblemsIEEE complexity I7l Lee DT, Lin AK, 1986.Computational pp vol. 276'282. on Information TheoryArchive, 32, Transaction D, HeckerHD, 1995-Two NP-hardairga ery problesfor orth{:,onal l8l Schuchardt polygors.Mathematical LogicQuanely , \ ol.41, pp.261 267 T Toussaint G, Zhu B. T997.Guardingpo yhedralterrarns Bose P, Shermer l9l Geonetry,vol 7, pp. 173-185. Computationai at DL,VeroyR, winslowA. 2011.Fac€guardsfor artgaLeriespresented [10]Souvaine Spanlsh Geometry, on Computaiioral the XIV Spanishl\,4eeting [11]CoxeterHSLI.1973.Regularpatytopes.NewYotk:DoverPublcations. sum ofvoumes Pan 1: aspects of alternating [12]TangK,WooTC.1991.Algorjthnric Dala structufeand differenceope?lian-ConputerAidedDesign,\o) 23 pp 357' 366. F. 2006. On visibilityproblemsin the plane ll3lTornas AP, BajuelosAL, I\,4arques approxiriaUonin the gth Int solvingminimumvertexguard problemsby successive Symp.on Artif.lniel.and lMath. on the Variations of postingseniries: RP, KimCE. 1988.Problems [14]Krishnaswamy iheory' wotkshop on algonthm Scandinavian ad gallerytheorem.in Proceedlngsof pp.74-85. p on and TheirRelaiionsh [15]MarzalJ, Xie H, FungCC. 2011.VeriexCofflsLrrations OrthogoaalPseudo Palyhed?. Warld Acadeny of Sclence,Engineeringarld pp. 1-aTechnology Yelas Berin Heidelbergl Atgarithms. FV, Kralsch D.2O1A.ExactExponentiat Fomin [16] Springer. Set Coverifg:Applicatron of l\.4inlnrum modeling llTlBuezasD. 2010.Constraint-based Nova Llniversdade de nlomaica, Master, Depanarnento io Sp€cies Differentation. de Lisboa, Lisboa.
