Shortest path and minimal link path

V diplomski nalogi opišemo algoritem za iskanje najkrajše poti v večkotniku in algoritem za iskanje poti z najmanj ovinki. Algoritma delujeta v večkotniku, katerega triangulacijo že poznamo. Prvi algoritem direktno uporablja triangulacijo. Drugi algoritem pri iskanju poti z najmanj ovinki poišče večkotnike vidljivosti. Pri tem si pomaga z najkrajšo potjo iz prvega algoritma. Opišemo tudi več algoritmov za konstruiranje večkotnikov vidljivosti. Algoritem za najkrajšo pot sem tudi implementiral v obliki mobilne aplikacije.In this thesis we describe an algorithm for computing the shortest path between two points in a simple polygon and an algorithm for computing a minimum link path between two points in a simple polygon. Both algorithms require that a triangulation of the polygon is already given. The first algorithm uses the triangulation directly, while the algorithm for the minimal link path makes use of the shortest path already computed with the first algorithm in order to compute visibility polygons. We also describe several algorithms for computing visibility polygons. I also implemented the algorithm for computing shortest path as a mobile application