| VRSTA GRADIVA | analitična raven (sestavni del), tekstovno gradivo, tiskano, 1.03 - kratki znanstveni prispevek |
| DRŽAVA IZIDA | Slovenija |
| LETO IZIDA | 2002 |
| JEZIK BESEDILA/IZVIRNIKA | angleški |
| PISAVA | latinica |
| AVTOR | Kaučič, Branko - avtor |
| ODGOVORNOST | Žalik, Borut - avtor |
| NASLOV | Correction of lower bound for guarding polyhedral terrains |
| V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ2, ǂno. ǂ1 (2002), str. 1-11. |
| KRATKA VSEBINA | Guarding polyhedral terrain is a relatively young problem in computational geometry. From the very first beginning it is know as NP-hard. The problem has been mainly treated theoretically to determine the optimal worst case number of guards. The last known bounds for the number of guards were determined by Bose et al. [2] in 1997. At thesame time, an open problem was set if someone can improve those bounds. In the paper, we show that sometimes needed number of edge guards (lower bound) has been set wrong. After revising the know estimate of sometimes needed number of edge guards, a corrected estimate is given. Consequently, a new open problem is set. // Varovanje poliederskih terenov je relativno mlad problem v računalniški geometriji. Že od samih začetkov je znano, da gre za NP-težek problem. Problem je bil v glavnem obravnavan teoretično, daso bile določene optimalne ocene števila stražarjev v najslabših primerih. Zadnje znane ocene števila stražarjev je leta 1997 določil Bose z ostalimi avtorji [2]. Istočasno je bil v svet plasiran odprti (nerešen) problem ali lahko kdo izboljša te ocene. V prispevku bomo pokazali, da je bila ocena včasih potrebnega števila stražarjev (tj. spodnja meja) postavljena napačno. Po reviziji znane ocene včasih potrebnega števila robovnih stražarjev, bomo podali popravljeno (pravilno) oceno. Posledično bomo postavili nov odprti problem. |
| OPOMBE | Bibliografija: str. 10-11 |
| OSTALI NASLOVI | Popravek spodnje meje v oceni števila stražarjev za varovanje poliederskih terenov |
| PREDMETNE OZNAKE | // računalniška geometrija // teorija grafov |
| UDK | 004.9:514.116 |