-
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document -
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document -
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Description
A robot navigates in a polygonal region populated by a set of partially distinguishable landmarks. The robot's motion primitives consist of actions of the form ``drive toward a landmark of class x''. To effectively navigate, the robot must always be able to see a landmark. Also, if the robot sees two landmarks of the same class, its motion primitives become ambiguous. Finally, if the robot wishes to navigate from landmark s_0 to landmark s_{goal} with a simple graph search algorithm, then there must be a sequence of landmarks [s_0,s_1,s_2,...,s_k=s_{goal}], in which landmark s_i is visible from s_{i-1}. Given these three conditions, how many landmark classes are required for navigation in a given polygon P? We call this minimum number of landmark classes the connected landmark class number, denoted chi_{CL}(P). We study this problem for the monotone polygons, an important family of polygons that are frequently generated as intermediate steps in other decomposition algorithms. We demonstrate that for all odd k, there exists a monotone polygon M_k with (3/4)(k^2+2k+1) vertices such that chi_{CL}(P) geq k. We also demonstrate that for any n-vertex monotone polygon P, chi_{CL}(P) leq n/3+12.