سمینار کارشناسی ارشد علوم کامپیوتر: یک شنبه 10 اردیبهشت 1391، ساعت 12

بسمه تعالی
سمینار کارشناسی ارشد علوم کامپیوتر
 
عنوان :
Hardness results for translating
congruent disks in the plane
سخنران:
خانم مهدیه قصابی  
زمان:
یکشنبه ۱۰ اردیبهشت ۱۳۹۱، ساعت ۱۲
مکان:
کلاس ۳۰۴ - دانشکده ریاضی
 
چکیده:
Consider a set of  pairwise interior-disjoint objects in the plane that need to be brought from a given start configuration  into a desired target configuration , without causing collisions. The reconfiguration problem for such a system is that of computing a sequence of object motions that achieves this task.
The reconfiguration problem is a simplified version of the multi-robot motion planning problem, in which a system of robots are operating together in a shared workplace and once in a while need to move from their initial positions to a set of target positions.
Translation model is a type of reconfiguration problems. In the translation model, one move is translating an object to another location in the plane along a fixed direction without colliding with any other object.
The reconfiguration problem in translation model for congruent disks is: Given a start configuration and a target configuration, each with  congruent disks in the plane, and a positive integer , is there a reconfiguration motion plan with at most  translating moves?
We show that the reconfiguration problem with congruent disks in the translation model, in both the labeled and unlabeled variants, is NP-hard.

-->