| |
|
Visualisation of Path-Finding for Robot
Sykala, Vít ; Orság, Filip (referee) ; Rozman, Jaroslav (advisor)
This bachelor´s thesis is explanation of algorithms for finding and planning robot motion in known space. First part is about margin and explanation of algorithms: Roadmaps and Cell decomposition. Next part is about progress of creating Java applets for visualization of these methods. Visualization of create Visibility graph and Trapezoidal decomposition in the concrete. Web presentation about these algorithms was too created as a part of this bachelor´s thesis. Here can be seen described Java applets.
|
| |
|
Viditelnostní grafy
Král, Karel ; Valtr, Pavel (advisor) ; Balko, Martin (referee)
In the thesis we study visibility graphs focusing on the Big Line Big Clique conjecture. For a given finite point set P in real plane we say that two points see each other if and only if the open line segment between them contains no point from P. Points from P are vertices of the visibility graph, and two points are connected by an edge if and only if they see each other. Kára et al. conjectured that for every finite big enough point set there are at least ℓ collinear points, or the clique number of its visibility graph is at least k. In the thesis we generalize the conjecture, and thus provide an alternative proof for k = ℓ = 4. We also review related known results. We strengthen an observation about occurrence of a Hamiltonian cycle in visibility graphs. We characterize the asymptotic behavior of the edge chromatic number of visibility graphs. We show that for given n, ℓ, k the original conjecture is decidable by a computer. We also provide computer experiments both for the generalized and for the original conjecture. 1
|
|
Visualisation of Path-Finding for Robot
Sykala, Vít ; Orság, Filip (referee) ; Rozman, Jaroslav (advisor)
This bachelor´s thesis is explanation of algorithms for finding and planning robot motion in known space. First part is about margin and explanation of algorithms: Roadmaps and Cell decomposition. Next part is about progress of creating Java applets for visualization of these methods. Visualization of create Visibility graph and Trapezoidal decomposition in the concrete. Web presentation about these algorithms was too created as a part of this bachelor´s thesis. Here can be seen described Java applets.
|