| 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 | ǂA ǂnew approach for vertex guarding of polyhedral surfaces |
| V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ2, ǂno. ǂ5 (2002), str. 1-16. |
| KRATKA VSEBINA | Guarding polyhedral surfaces is an important optimisation problem with many applications. In the contribution, the problem of finding the minimum number of guards and their positions, which cover a convex terrain is considered. Known approximative algorithms (Greedy Add, Stingy Drop, and the algorithm based on 5-coloring) are revised and a new approach names Smart Greedy algorithm is given. The algorithm works in three steps: identification of the vertex that is almostsure not a part of the optimum solution, selection of the vertex that is almost sure a part of the optimum solution, and updating a corresponding data structure. The proposed algorithm is compared against optimality of solutions and spent running time. It is shown that our algorithm produces best results in the shortest time. // Varovanje poliederskih površij je pomemben optimizacijski problem z veliko aplikacijami. V prispevku je obravnavan problem iskanja minimalnega števila stražarjev in njihovega položaja pri varovanju konveksnih terenov. Obravnavani so znani aproksimativni algoritmi (Greedy Add, Stingy Drop, in algoritem na podlagi 5-barvanja) in podan je nov pristop imenovan Smart Greedy algoritem. Algoritem deluje v treh korakih: identifikacija oglišča, ki skoraj zagotovoni del optimalne rešitve, izbira oglišča, ki skoraj zagotovo je del optimalne rešitve in posodabljanje pripadajoče podatkovne strukture. Predlagan algoritem je primerjan glede optimalnosti rešitev in porabljen izvajalni čas. Pokazano je, da naš algoritem producira najboljše rezultate v najkrajšem času. |
| OPOMBE | Bibliografija: str. 16 |
| OSTALI NASLOVI | Nov pristop ogliščnega varovanja poliederskih površij |
| PREDMETNE OZNAKE | // računalniška geometrija // teorija grafov // optimizacija // algoritmi |
| UDK | 004.92:519.17 |