20.500.12556/RUL-173404 Najmanjši $k$-točk obdajajoči pravokotnik delo diplomskega seminarja Smallest $k$-point enclosing rectangle V računski geometriji se pogosto pojavi naslednji problem: za dano množico točk želimo določiti najmanjši geometrijski objekt neke vrste, ki jo vsebuje. Naravna razširitev problema je, da uvedemo parameter $k$, pri čemer nas zanima najmanjši objekt, ki vsebuje $k$ točk. To nas vodi do problema najmanjšega $k$-točk obdajajočega pravokotnika. Cilj diplomskega dela je predstaviti preprost algoritem tipa deli in vladaj, ki trenutno velja za najboljšega. Ogledamo si tudi različne razširitve problema in pokažemo, kako se na njih prilagodi osnovna metoda, pri tem pa ohrani svojo učinkovitost. In computational geometry the following problem often arises: given a set of points, determine the smallest geometric shape of a certain type that contains them. A natural variation introduces a parameter $k$, asking for a shape that contains k points rather than all of them. This leads to the smallest $k$-point enclosing rectangle problem. In this thesis, we present a simple divide-and-conquer approach which is currently the state of the art. We also study several extensions of the problem and show how the method adapts while retaining its efficiency. računska geometrija obdajajoči pravokotnik deli in vladaj computational geometry bounding box divide and conquer true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-09-17 08:15:11 2025-09-17 08:15:13 2025-11-08 04:00:33 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.8 153721 249905155 19062.pdf 19062.pdf 1 981C5185D0BD81364433ADF133EC7F36 4d4f54afb3c2cb7178bb08a410ab378866ca496775db2ef64785c39dd7c740ea 7f8c9977-938d-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217814 Fakulteta za matematiko in fiziko 0 0 0